Taro Logo

Binary Tree Inorder Traversal

Easy
Uber logo
Uber
1 view
Topics:
TreesRecursionStacks

Given the root of a binary tree, can you implement an algorithm to return the inorder traversal of its nodes' values? Inorder traversal visits the left subtree, then the root, and finally the right subtree.

For example, consider the following binary tree:

    1
     \
      2
     /
    3

An inorder traversal of this tree would be [1, 3, 2].

Here's another example:

    1
   / \
  2   3
 / \   \
4   5   8
   / \
  6   7

An inorder traversal of this tree would be [4, 2, 5, 1, 3, 8].

What are some edge cases we should consider? How would you approach this problem using both recursive and iterative methods? What are the time and space complexities of each approach? Can you provide code examples for both methods?

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the range of values for the nodes in the binary tree? Can they be negative?
  2. Can the tree be empty (i.e., root is null)? If so, what should I return?
  3. Are the node values unique, or can there be duplicate values in the tree?
  4. What is the expected data type of the node values? (e.g., integer, string, etc.)
  5. Is the binary tree guaranteed to be a binary search tree, or is it a general binary tree?

Brute Force Solution

Approach

Binary tree inorder traversal means visiting the tree's nodes in a specific order: left, then the node itself, then right. A brute force method means trying every possible path and order until we get to the proper sequence, effectively exploring every nook and cranny of the tree.

Here's how the algorithm would work step-by-step:

  1. Start at the very top of the tree, which is called the root.
  2. First, let's see what happens if we process the left side of the tree immediately. Explore every possible branch on the left side before doing anything else.
  3. Keep going left until you can't go any further. Then, when you are at the end of a branch, you will 'visit' that node; by visiting, we mean add it to our sequence.
  4. After visiting the node from the left branch, go to that node's right branch. Repeat the process for the right branch of exploring it until you can not go further left.
  5. If there is no right branch, you are done with that node, and you need to go back to the node that led you here to continue. This will ensure we have gone through the current left, current node, and current right sequence for all nodes.
  6. Keep track of all the nodes in the order you visited them. This list will show all possible traversals based on our left, node, and right sequence rules.
  7. Make sure the sequence is correct. The brute force approach will require us to trace the output to see if we missed nodes or added them in the wrong order, as well as trying different orders when possible.

Code Implementation

class TreeNode: 
    def __init__(self, value=0, left=None, right=None): 
        self.value = value
        self.left = left
        self.right = right

def binary_tree_inorder_traversal_brute_force(root):
    all_possible_traversals = []
    current_traversal = []

    def explore_tree(node):
        nonlocal current_traversal, all_possible_traversals

        if node:
            # Explore the left subtree first
            explore_tree(node.left)

            current_traversal.append(node.value)

            # Explore the right subtree
            explore_tree(node.right)

    explore_tree(root)
    all_possible_traversals.append(current_traversal[:])

    return all_possible_traversals[0]

Big(O) Analysis

Time Complexity
O(n)The inorder traversal visits each node in the binary tree exactly once. While the brute force approach explores different paths and potentially revisits nodes to ensure correctness, the fundamental operation of adding each node to the sequence happens only once per node. Therefore, the number of operations is directly proportional to the number of nodes in the tree, which we denote as n. This results in a linear time complexity of O(n).
Space Complexity
O(N)The brute force inorder traversal, as described, implicitly relies on recursion. Each recursive call adds a new frame to the call stack to keep track of the current state of exploration. In the worst-case scenario, where the binary tree is highly skewed (e.g., a linked list), the depth of the recursion can reach N, where N is the number of nodes in the tree. Therefore, the maximum space required for the recursion stack is proportional to the height of the tree, which in the worst case is N, resulting in O(N) auxiliary space.

Optimal Solution

Approach

Inorder traversal visits a binary tree's nodes in a specific order: left subtree, current node, then right subtree. The best way to do this is using a stack to keep track of where we need to go back to after exploring a left branch. It avoids recursion and does not need extra memory for the stack.

Here's how the algorithm would work step-by-step:

  1. Start at the very top (root) of the tree.
  2. Keep going left as far as possible. Each time you move left, remember the current node by placing it on a stack.
  3. Once you can't go left anymore (you've hit a dead end), take the top node from the stack. This is the leftmost node.
  4. Process (record or visit) this node's value.
  5. Now, look to this node's right child. If there is a right child, start the whole process again from that right child (go as far left as possible, putting nodes on the stack).
  6. If there's no right child, simply go back to the stack and get the next node.
  7. Keep repeating steps 3-6 until the stack is empty and you've looked at the right child of the very last node in the stack.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root):
    result = []
    stack = []
    current_node = root

    while current_node or stack:
        # Traverse left subtree and push nodes onto the stack.
        while current_node:
            stack.append(current_node)

            current_node = current_node.left

        # Backtrack: process the node and move to the right subtree.
        current_node = stack.pop()

        # We have the leftmost node, add its value to results.
        result.append(current_node.val)

        current_node = current_node.right

    return result

Big(O) Analysis

Time Complexity
O(n)The algorithm visits each node in the binary tree exactly once. The while loop continues as long as either the current node is not null or the stack is not empty. In each iteration, either a node is pushed onto the stack (when traversing left), or a node is popped from the stack (when processing a node), or the current node is updated to its right child. Each node is pushed and popped from the stack at most once. Therefore, the number of iterations is proportional to the number of nodes, n, in the tree. Thus, the time complexity is O(n).
Space Complexity
O(H)The iterative inorder traversal utilizes a stack. The maximum number of nodes that can be present in the stack at any given time corresponds to the height of the binary tree, denoted as H. In the worst-case scenario, such as a skewed tree, the height can be equal to N (number of nodes). Therefore, the auxiliary space required for the stack is proportional to the height of the tree, H, which translates to O(H) space complexity.

Edge Cases

CaseHow to Handle
Null or empty root nodeThe function should return an empty list if the root is null to represent an empty tree.
Single node tree (root only)The function should return a list containing only the value of the root node.
Tree with only left childrenThe inorder traversal should correctly visit all left children and then the root, in the specified order.
Tree with only right childrenThe inorder traversal should correctly visit the root and then all right children, in the specified order.
Complete binary treeThe inorder traversal should correctly visit all nodes in the correct order (left, root, right for each subtree).
Large, balanced binary treeRecursive solutions could face stack overflow issues; iterative solutions with an explicit stack may be preferred for larger trees.
Binary Search Tree (BST) - inorder traversal should return a sorted list.Check if the output list from the inorder traversal is sorted when the input is a BST.
Tree with duplicate valuesThe traversal should handle duplicate values without any issues, including them in the correct order within the output list.