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?
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:
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:
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]
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:
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
Case | How to Handle |
---|---|
Null or empty root node | The 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 children | The inorder traversal should correctly visit all left children and then the root, in the specified order. |
Tree with only right children | The inorder traversal should correctly visit the root and then all right children, in the specified order. |
Complete binary tree | The inorder traversal should correctly visit all nodes in the correct order (left, root, right for each subtree). |
Large, balanced binary tree | Recursive 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 values | The traversal should handle duplicate values without any issues, including them in the correct order within the output list. |