grid47 Exploring patterns and algorithms
Oct 28, 2024
5 min read
Solution to LeetCode 94: Binary Tree Inorder Traversal Problem
Given the root of a binary tree, return the values of its nodes as they appear in an inorder traversal. Inorder traversal visits nodes in the left subtree, the root, and then the right subtree.
Problem
Approach
Steps
Complexity
Input: The input is the root of a binary tree where each node has a value and pointers to left and right child nodes.
Example: Input: root = [5,3,8,1,4,null,10]
Constraints:
• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100
Output: Return a list of integers representing the inorder traversal of the binary tree.
Example: Output: [1,3,4,5,8,10]
Constraints:
• The output list must contain the values of all nodes visited in correct inorder sequence.
Goal: Perform an inorder traversal of the binary tree and return the node values in the correct order.
Steps:
• Traverse the left subtree recursively.
• Visit the root node and append its value to the result list.
• Traverse the right subtree recursively.
Goal: Ensure that the traversal correctly handles binary trees with various structures.
Steps:
• Handle null nodes gracefully.
• Ensure the solution works for trees with all node values at the boundaries of the valid range.
Assumptions:
• The input tree is binary (each node has at most two children).
• The input tree structure is well-formed, with nodes correctly linked.
• Input: Input: root = [2,1,3]
• Explanation: The inorder traversal visits nodes in the order: left (1), root (2), right (3). Output: [1,2,3].
• Input: Input: root = [10,null,15,null,20]
• Explanation: The inorder traversal visits nodes in the order: root (10), right child (15), right subtree (20). Output: [10,15,20].
• Input: Input: root = []
• Explanation: An empty tree has no nodes to traverse. Output: [].
• Input: Input: root = [7]
• Explanation: A single-node tree has only the root to traverse. Output: [7].
Approach: Perform an inorder traversal of the binary tree using both recursive and iterative methods.
Observations:
• Inorder traversal visits nodes in the order: left subtree, root, right subtree.
• A recursive implementation is straightforward but can be replaced with an iterative stack-based approach for better control over recursion depth.
• Iterative traversal avoids the function call stack and provides explicit stack management.
• Both methods result in the same output but vary in implementation style and use of memory.
Steps:
• Initialize an empty list to store the result and a stack to manage traversal states.
• Push nodes onto the stack while traversing to the leftmost node.
• Pop nodes from the stack, append their value to the result, and traverse their right child.
• Repeat until all nodes are visited.
Empty Inputs:
• An empty tree (root = null) should return an empty list.
Large Inputs:
• A tree with maximum nodes (100) with a balanced or unbalanced structure.
Special Values:
• All node values are the same, e.g., root = [5,5,5].
• All nodes are arranged in a single line (left-skewed or right-skewed tree).
Constraints:
• Ensure no extra nodes are added or skipped during traversal.
Declares a function `inorderTraversal` that takes the root node of a binary tree as input and returns a vector containing the inorder traversal of the tree.
2 : Result Initialization
vector<int> nodes;
Initializes an empty vector `nodes` to store the inorder traversal result.
3 : Stack Initialization
stack<TreeNode*> todo;
Initializes an empty stack `todo` to keep track of nodes to be visited.
4 : Loop Iteration
while (root ||!todo.empty()) {
Iterates until both the `root` node and the `todo` stack are empty.
5 : Nested Loop Iteration
while (root) {
While the current `root` node is not null, we keep pushing it onto the stack and moving to its left child.
6 : Stack Push
todo.push(root);
Pushes the current `root` node onto the stack.
7 : Pointer Update
root = root -> left;
Moves the `root` pointer to its left child.
8 : Stack Pop
root = todo.top();
Pops the top node from the stack and assigns it to the `root`.
9 : Stack Pop
todo.pop();
Removes the top node from the stack.
10 : Result Update
nodes.push_back(root -> val);
Adds the value of the current `root` node to the `nodes` vector.
11 : Pointer Update
root = root -> right;
Moves the `root` pointer to its right child.
12 : Return
return nodes;
Returns the `nodes` vector containing the inorder traversal of the tree.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: Each node is visited exactly once during the traversal.
Best Case: O(1)
Worst Case: O(n)
Description: In the worst case, the stack stores all nodes (e.g., in a completely skewed tree).
