XYZ CODE: Binary Tree Inorder traversal

Problem

Given a binary tree, return the inorder traversal of its nodes' values.

For Example:

Given:
1
\
2
/ \
3 4

Output: [1,3,2,4]
Follow up: are you able to do it iteratively?

Solution

The inorder recursive traversal took O(N) time cost to visit all the nodes. The caller stack is ~logN on average and N at worst, each stack has finite number of variables. so that gives the space cost O(logN) to O(N).

For iterative solution, we need to store lots of nodes before we can start to print. We can store in queue or stack, queue is first-in last-out, won't work here. Stack is closer to what we are trying to do. When we traversal to the first node to print, we can store the nodes on the route to a stack. After we print, we use the stack to trace back. After we pop out a node, we store it, before pop out another node, we should process the right node. We do the same thing, store all the node in the stack before we move to the first node to print, then we trace back. Each node is push in and pop out of the stack once, the time cost is O(N). The space is bound by the stack size, which is O(N).

bst inorder traversal

import java.util.*;
class InOrder{
public static void recurInOrder(Node root, List<Integer> inOrder) {
if(root == null) return;
recurInOrder(root.left, inOrder);
inOrder.add(root.value);
recurInOrder(root.right, inOrder);
}
public static void iterInOrder(Node root, List<Integer> inOrder) {
Stack<Node> stack = new Stack<>();
while(root != null) {
stack.push(root);
root = root.left;
}
while(!stack.isEmpty()) {
Node t = stack.pop();
inOrder.add(t.value);
t = t.right;
while(t != null) {
stack.push(t);
t = t.left;
}
}
}
public static void main(String...args) {
Node root = new Node(1, null, new Node(2, null, new Node(3, null, null)));
List<Integer> inOrder = new ArrayList<>();
recurInOrder(root, inOrder);
for(int i : inOrder) {
System.out.print(i + " ");
}
System.out.println();
inOrder = new ArrayList<>();
iterInOrder(root, inOrder);
for(int i : inOrder) {
System.out.print(i + " ");
}
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}

Time cost O(N), space cost O(N).