Search
Binary Tree Traversal
Last updated
Jan 2, 2022
Edit Source
# With recursion
With recursion, it pretty straightforward, here is an example java code:
1
2
3
4
5
6
7
| public static void traverse(BinaryTree t, List<Integer> l){
if(t == null)
return;
traverse(t.getLeft(), l);
l.add(t.getKey());
traverse(t.getRight(), l)
}
|
# Without recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static void traverse(BinaryTree t, List<Integer> l){
Stack<BinaryTree> s = new Stack<>();
BinaryTree cur = t;
while(cur != null || !t.isEmpty()){
if(cur == null){
cur = s.pop();
l.add(cur.getKey());
cur = s.getRight();
}else{
s.push(cur);
cur = cur.getLeft();
}
}
}
|