/ Data Structure and Algorithms  

Leetcode 94. Binary Tree Inorder Traversal

Question



In-order traversal of a binary tree.

Similar Questions

Solution - Recursive

Using recursion to traverse a binary tree. This is one of the standard approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();

    getAnswer(root, result);

    return result;
}

// standard way to traverse tree inorder. Recursive
private static void getAnswer(TreeNode node, List<Integer> result) {
    if (node == null) {
        return;
    }

    getAnswer(node.left, result);
    result.add(node.val);
    getAnswer(node.right, result);
}

Time complexity: O(n), traverse each node.

Space complexity: O(h), stack consumption, h is the height of the binary tree.

Solution - Stack

Use the stack to simulate recursion.

Let’s look at an example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
        1
      /   \
     2     3
    / \   /
   4   5 6

 push   push   push   pop     pop    push     pop     pop 
|   |  |   |  |_4_|  |   |   |   |  |   |    |   |   |   |  
|   |  |_2_|  |_2_|  |_2_|   |   |  |_5_|    |   |   |   |
|_1_|  |_1_|  |_1_|  |_1_|   |_1_|  |_1_|    |_1_|   |   |
ans                  add 4   add 2           add 5   add 1
[]                   [4]     [4 2]           [4 2 5] [4 2 5 1]
 
 push   push   pop          pop 
|   |  |   |  |   |        |   |  
|   |  |_6_|  |   |        |   |  
|_3_|  |_3_|  |_3_|        |   |
              add 6        add 3
              [4 2 5 1 6]  [4 2 5 1 6 3]

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();

TreeNode current = root;
while (current != null || !stack.isEmpty()) {
    // node is not null, push to stack
    // push left first
    while (current != null) {
        stack.push(current);

        current = current.left;
    }

    // node is null, pop
    current = stack.pop();

    // add to result
    result.add(current.val);

    // consider right tree
    current = current.right;
}

return result;

Time complexity: O(n), traverse each node.

Space complexity: O(h), stack consumption, h is the height of the binary tree.

Solution - Morris traversal

Morris traversal