Understanding the Problem
In this problem, we are asked to perform a preorder traversal of a binary tree. This means we want to visit all the nodes in the following specific order: root → left → right.
Binary trees can come in many shapes — balanced, skewed, or even empty — and our goal is to ensure that regardless of the shape, we always return a list of node values in this preorder sequence.
We’ll use a recursive approach that mimics how a human would traverse the tree: start at the root, explore the entire left side, then move to the right side.
Step-by-Step Solution with Example
Step 1: Visualize the Tree
Let's take the example of the following binary tree:
1
/ 2 3
/ 4 5
The preorder traversal should visit: 1 → 2 → 4 → 5 → 3
Step 2: Understand the Preorder Rule
The rule for preorder traversal is:
- Visit the root node
- Recursively do a preorder traversal of the left subtree
- Recursively do a preorder traversal of the right subtree
Step 3: Write the Recursive Logic
We’ll define a function that:
- Checks if the current node is null (base case)
- If not null, adds the node’s value to the result list
- Recursively calls itself for the left child
- Then recursively calls itself for the right child
Step 4: Apply the Logic to the Example
Start from root 1
:
- Add
1
to result
- Go left to
2
, add to result
- Go left to
4
, add to result. Left and right are null → backtrack
- Go right to
5
, add to result. Left and right are null → backtrack
- Back to
1
, go right to 3
, add to result
Final result: [1, 2, 4, 5, 3]
Edge Cases
Empty Tree
If the tree is empty (i.e., root is null
), we return an empty list: []
Single Node Tree
If there is only one node (no left or right child), return a list with just that node's value: [root.val]
Left-Skewed Tree
Each node only has a left child. The result will be a top-to-bottom list from root to the last left node.
1
/
2
/
3
Traversal: [1, 2, 3]
Right-Skewed Tree
Each node only has a right child. The result will be a top-to-bottom list from root to the last right node.
1
2
3
Traversal: [1, 2, 3]
Finally
Preorder traversal is all about visiting nodes in the order: root → left → right. With recursion, this pattern becomes very natural to implement, and it handles all tree structures gracefully.
By breaking the tree into smaller subproblems (left and right subtrees), we simplify the traversal process. Always remember to check for null nodes to handle edge cases smoothly.
This recursive strategy will consistently give us the correct preorder output for any binary tree.
Comments
Loading comments...