Optimize traversal for without recursion

Question

Given a binary tree, implement a function to traverse the tree in-order without using recursion. The function should take the root node of the tree as input and return a list of values representing the in-order traversal of the tree nodes.

Codemia · Accepted Answer

In this problem, we need to perform an in-order traversal of a binary tree without using recursion. The in-order traversal visits nodes in the following order: left subtree, current node, right subtree. The challenge here is to manage the traversal using an iterative approach rather than recursion, which typically uses the call stack to remember the nodes. For this, we can utilize a stack data structure to keep track of nodes as we traverse the tree.

1. Initialize an empty stack to keep track of nodes and an empty result list to store the traversal order.
2. Start from the root node and push all the left nodes onto the stack until you reach a null node.
3. Once you hit a null node, pop the top node from the stack, add its value to the result list, and then push its right child onto the stack.
4. Repeat the process until both the stack is empty and you have no more nodes to visit.

**Example:** Given the binary tree:
```
    1
   / \
  2   3
 / 
4
```
The in-order traversal would be: [4, 2, 1, 3].

Here is the Python code implementing the iterative in-order traversal:
```python
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 = root

while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right

return result
```
This code effectively uses a stack to manage the nodes and provides the correct in-order traversal.

The time complexity of this iterative in-order traversal is O(n), where n is the number of nodes in the binary tree. This is because each node is pushed and popped from the stack exactly once. The space complexity is O(h), where h is the height of the tree. In the worst case of a skewed tree, the height could be n, but in a balanced tree, it would be log(n).

1. **Empty Tree:** If the input tree is empty (i.e., root is None), the function should return an empty list `[]`.
2. **Single Node Tree:** If the tree has only one node, the output should be a list containing that single value.
3. **Skewed Trees:** The algorithm should handle both left-skewed and right-skewed trees correctly, ensuring that the traversal still follows the in-order sequence.

Optimize traversal for without recursion

DoorDash

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

DoorDash Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string