1028. Recover a Tree From Preorder Traversal - Detailed Explanation
Problem Statement
Given a string representing the preorder traversal of a binary tree, where each node is an integer and the depth of each node is indicated by the number of preceding dashes, recover and construct the original binary tree. The first number (without any dashes) represents the root, and every subsequent node is at a depth equal to the number of dashes immediately preceding its value.
For example, given the string "1-2--3--4-5--6--7", the tree is constructed as:
1
/ \
2 5
/ \ / \
3 4 6 7
Example
Example 1
- Input:
"1-2--3--4-5--6--7" - Output: The tree with root 1, where:
- 1's left child is 2 and right child is 5.
- 2's left child is 3 and right child is 4.
- 5's left child is 6 and right child is 7.
Example 2
- Input:
"1-401--349---90-88" - Output: The tree with root 1, where:
- 1's left child is 401.
- 401's left child is 349 and right child is 88.
- 349's left child is 90.
Explanation: The number of dashes before each number indicates its depth in the tree.
Hints
- Parsing the String:
Each node in the tree is represented as a sequence of dashes followed by a number. The number of dashes indicates the depth level of that node. - Using a Stack:
A stack can be used to maintain the path from the root to the current node. When a node with depthdis encountered, pop nodes from the stack until the stack size equalsd. The new node is attached as a child of the current top of the stack. - Left vs. Right Child:
For each node, if it does not already have a left child, attach the new node as its left child; otherwise, attach it as its right child.
Approaches Overview
Approach 1: Recursive Parsing
- Idea:
Recursively parse the string by reading the number of dashes to determine depth and then reading the numeric value for the node. - Process:
- Write a recursive function that takes the current depth and the string index.
- For the current index, count the dashes; if they match the expected depth, parse the number.
- Recursively call for left and right subtrees with an increased depth.
- Consideration:
Managing the string index across recursive calls can be tricky.
Approach 2: Iterative Using a Stack
- Idea:
Parse the string iteratively and use a stack to keep track of the current path from the root. - Process:
- Iterate through the string to extract each node's depth (by counting dashes) and value.
- While the stack’s size is greater than the current node’s depth, pop from the stack.
- Attach the new node as the left child if the parent does not have one; otherwise, attach as the right child.
- Push the new node onto the stack.
- Advantage:
This method efficiently handles the tree reconstruction in a single pass.
Python Implementation
Java Implementation
Explanation Recap
-
Parsing the String:
Both implementations iterate through the input string. For each node:- The number of preceding dashes is counted to determine the node's depth.
- The following sequence of digits is parsed to get the node's value.
-
Using a Stack:
A stack is used to store the current path of nodes. When a new node is parsed, the stack is adjusted (popping extra nodes) so that the size of the stack matches the current node’s depth. Then the new node is attached as a left child (if available) or as a right child. -
Returning the Tree:
At the end, the bottom element of the stack is the tree's root, which is returned.
This stack-based approach efficiently reconstructs the binary tree from the preorder traversal string in one pass, with a time complexity of O(n) and a space complexity of O(n).
Detailed Step-by-Step Explanation (Stack Approach)
-
Initialize:
Create an empty stack. The first number (with no dashes) is the root node; create the node and push it onto the stack. -
Parsing and Node Creation:
For each subsequent segment in the string:- Determine Depth:
Count the consecutive dashes (-) to determine the depthdof the new node. - Parse Value:
Read the digits following the dashes to extract the numeric value. - Adjust the Stack:
If the stack’s current size is greater thand, pop from the stack until the size equalsd. - Attach Node:
The current top of the stack is the parent. If the parent does not have a left child, attach the new node as the left child; otherwise, attach it as the right child. - Push the New Node:
Push the new node onto the stack.
- Determine Depth:
-
Completion:
Once the entire string is processed, the root of the tree is the first element that was pushed (or can be obtained from the bottom of the stack).
Complexity Analysis
-
Time Complexity: O(n)
We traverse the input string once. Each character (dash or digit) is processed exactly once. -
Space Complexity: O(n)
In the worst case, the stack may hold a number of nodes equal to the height of the tree, which in the worst-case (a skewed tree) is O(n).
Common Mistakes
-
Incorrect Dash Counting:
Failing to accurately count the dashes may result in wrong depth calculation. -
Improper Stack Management:
Not popping the stack when the current node’s depth is less than the stack size leads to incorrect parent-child relationships. -
Parsing Errors:
Converting substring segments to integers incorrectly can cause runtime errors.
Alternative Variations
-
Recursive Approach:
Instead of an iterative stack-based method, use a recursive function that returns the constructed node and the next index to be processed. -
Different Traversal Formats:
The problem can be extended or modified for different traversal orders or when additional node information is provided.
GET YOUR FREE
Coding Questions Catalog
