1028. Recover a Tree From Preorder Traversal
Problem Description
The task is to reconstruct a binary tree given the preorder traversal string where each node in the string is represented by a number of dashes equivalent to the node's depth in the tree followed immediately by the node's value. In the provided string, the depth of the root node is 0, meaning it starts with no dashes, and successive nodes have increasing numbers of dashes depending on their depth. Importantly, if a node has only one child, that child is always the left child.
Intuition
In the solution, a stack data structure is used to keep track of the nodes and their respective depths, leveraging the Last In, First Out (LIFO) property to manage the tree's structure as we iterate through the input string. We parse the string character by character, counting dashes to determine the depth of the next node and concatenating numbers to form the value of each node. Whenever we reach the end of a number (indicated by the next character being a dash or end of string), a new tree node is created.
The node's position in the tree is determined by comparing its depth with the size of the stack (which represents the current path down the tree). If the current depth is less than the size of the stack, we pop from the stack until the top of the stack is the parent of the new node, ensuring proper node placement according to the preorder sequence. If the stack is not empty, we link the new node as either the left or right child of the current top node on the stack, depending on the left child's presence. Then, we push the new node onto the stack, which allows us to pop back to it when its children are processed, ensuring the tree structure is correctly maintained. Finally, after processing the entire string, the stack's top holds the root of the rebuilt binary tree, which is returned.
Learn more about Tree, Depth-First Search and Binary Tree patterns.
How does merge sort divide the problem into subproblems?
Solution Approach
The solution approach uses a stack to retrace the steps of the preorder depth-first traversal that created the given string. Here's a step-by-step walk-through of the algorithm:
-
Initialize an empty stack
stto keep track of the nodes as they are created, representing the current path through the tree based on the depth-first nature of the traversal. Additionally, define the variablesdepthandnumto store the current depth and the value of the node being processed, respectively. -
Iterate through each character
iin the given stringS. If the current character is a dash'-', increment the depth counterdepth. If the current character is a digit, update the node valuenumby shifting the existing digits to the left (multiplying by 10) and adding the current digit's value. -
If the end of the node's value string is reached (either the end of
Sis reached or the next character is a dash), a node needs to be created with the accumulatednumvalue. This is done as follows:- Create a new tree node
newNodewith the valuenum. - Modify the stack to correspond to the proper depth by popping nodes until
st.size()equals the currentdepth. This ensures that the top of the stack is the parent node ofnewNode. - If the stack is not empty, attach
newNodeas a left child if the top node's left child isnullptr, otherwise as a right child. This aligns with the rule that singly childed nodes are left children. - Push
newNodeonto the stack. This node will become a parent to subsequent nodes in the traversal or will be popped if we backtrack to a lesser depth.
- Create a new tree node
-
After processing all characters, pop all remaining nodes from the stack until it's empty. The last node popped is the root node of the tree (
res), which is the correct return for a successful reconstruction of the tree according to the preorder traversal string. -
Return the root node
res.
This algorithm relies on understanding how preorder traversal works and simulating this process in reverse. This stack-based approach correctly aligns with the preorder traversal's property that parents are visited before their children, and it handles single-child subtrees by design, as the left child rule is directly enforced by the algorithm. The use of the stack allows us to track the path through the tree and ensures proper parent-child relationships.
How many times is a tree node visited in a depth first search?
Example Walkthrough
Let's use a small example to illustrate the solution approach.
Suppose we are given the following preorder traversal string of a binary tree: "1-2--3--4-5--6--7". We need to reconstruct the corresponding binary tree from this string.
Steps to reconstruct the binary tree:
- Initialize an empty stack
st. - Begin with the first character in the string, which has no dashes in front, so it represents the root node with the value
1. Create this node and push it onto the stack. - Move on to the next character. We encounter a single dash and then the value
2. Since the depth indicated by dashes is1, we create the node with the value2, and since the stack's current depth is also1, this node is a left child of the top node on the stack. Attach node2as a left child of node1and push node2onto the stack. - The following four characters indicate a node with value
3and a depth of2. We pop node2off the stack since its depth is more than1, and add node3as the left child of the new top of the stack, which is node2. Push node3onto the stack. - Similarly, for the next node with a depth of
2and value4, we pop node3off the stack and attach node4as the right child of node2(since the left child is already present). Push node4onto the stack. - Proceed with characters
'-5--6--7'. We encounter node5with a depth of1, pop nodes until the stack depth matches1, and then attach node5as the right child of the root node1. Push node5onto the stack. - Node
6has a depth of2, so we pop node5to match the depth. Since node5has no left child, we attach node6as the left child. Push node6onto the stack. - Lastly, we handle node
7, which also has a depth of2. We pop node6and attach node7as the right child of node5. After pushing node7onto the stack, we finish processing the string.
The final step is to pop all remaining nodes from the stack until it is empty. The last node popped is the root node 1.
The binary tree that corresponds to the string "1-2--3--4-5--6--7" is now successfully reconstructed and is represented as:
1 1 2 / \ 3 2 5 4 / \ / \ 53 4 6 7
By following this process as outlined in the solution approach, we have moved character by character through the input string, maintained a current path through the tree with the stack, and updated parent-child relationships, finally arriving at the original binary tree.
Solution Implementation
1# Definition for a binary tree node.
2class TreeNode:
3 def __init__(self, x):
4 self.val = x
5 self.left = None
6 self.right = None
7
8class Solution:
9 def recoverFromPreorder(self, traversal: str) -> TreeNode:
10 # Create a stack to hold nodes and initialize depth and value variables.
11 nodes_stack = []
12 current_depth = 0
13 current_value = 0
14
15 # Loop through each character in the traversal string.
16 for i in range(len(traversal)):
17 if traversal[i] == '-':
18 # Increment the depth for every '-' character encountered.
19 current_depth += 1
20 else:
21 # Calculate the node's value.
22 current_value = 10 * current_value + (ord(traversal[i]) - ord('0'))
23
24 # Check for the end of number or end of string.
25 if i + 1 == len(traversal) or (traversal[i].isdigit() and traversal[i + 1] == '-'):
26 # Create a new node with the computed value.
27 new_node = TreeNode(current_value)
28
29 # If the stack size is greater than the current depth, pop until the sizes match.
30 while len(nodes_stack) > current_depth:
31 nodes_stack.pop()
32
33 # If the stack is not empty, assign the new node to the appropriate child of the top node.
34 if nodes_stack:
35 if nodes_stack[-1].left is None:
36 nodes_stack[-1].left = new_node
37 else:
38 nodes_stack[-1].right = new_node
39
40 # Push the new node onto the stack.
41 nodes_stack.append(new_node)
42
43 # Reset current depth and value for the next node.
44 current_depth = 0
45 current_value = 0
46
47 # The result is the root of the tree. It's the bottommost node in the stack.
48 result = None
49 while nodes_stack:
50 result = nodes_stack.pop()
51
52 # Return the reconstructed binary tree.
53 return result
541import java.util.Stack;
2
3// Definition for a binary tree node.
4class TreeNode {
5 int val;
6 TreeNode left;
7 TreeNode right;
8
9 TreeNode(int x) {
10 val = x;
11 left = null;
12 right = null;
13 }
14}
15
16class Solution {
17 public TreeNode recoverFromPreorder(String traversal) {
18 Stack<TreeNode> nodesStack = new Stack<>();
19 int currentDepth = 0;
20 int currentValue = 0;
21
22 for (int i = 0; i < traversal.length(); ++i) {
23 if (traversal.charAt(i) == '-') {
24 // Increment the currentDepth for each '-' character encountered
25 currentDepth++;
26 } else {
27 // Calculate the currentValue of the current node
28 currentValue = 10 * currentValue + (traversal.charAt(i) - '0');
29 }
30
31 // Check for the end of the number or the end of the string
32 if (i + 1 == traversal.length() || (Character.isDigit(traversal.charAt(i)) && traversal.charAt(i + 1) == '-')) {
33 TreeNode newNode = new TreeNode(currentValue);
34
35 // If the nodesStack size is greater than the currentDepth, we pop nodes until they match
36 while (nodesStack.size() > currentDepth) {
37 nodesStack.pop();
38 }
39
40 // If nodesStack is not empty, we link the newNode as a child to the node at the top of the stack
41 if (!nodesStack.isEmpty()) {
42 if (nodesStack.peek().left == null) {
43 nodesStack.peek().left = newNode;
44 } else {
45 nodesStack.peek().right = newNode;
46 }
47 }
48
49 // Push the newNode onto the stack
50 nodesStack.push(newNode);
51
52 // Reset currentDepth and currentValue for the next node
53 currentDepth = 0;
54 currentValue = 0;
55 }
56 }
57
58 // Result is the root of the binary tree, which is the bottommost node in the nodesStack
59 TreeNode result = null;
60 while (!nodesStack.isEmpty()) {
61 result = nodesStack.peek();
62 nodesStack.pop();
63 }
64
65 // Return the recovered binary tree
66 return result;
67 }
68}
691#include <cctype>
2#include <stack>
3#include <string>
4
5// Definition for a binary tree node
6struct TreeNode {
7 int val;
8 TreeNode *left;
9 TreeNode *right;
10 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11};
12
13class Solution {
14public:
15 TreeNode* recoverFromPreorder(std::string traversal) {
16 std::stack<TreeNode*> nodesStack;
17 int currentDepth = 0;
18 int currentValue = 0;
19
20 for (int i = 0; i < traversal.length(); ++i) {
21 if (traversal[i] == '-') {
22 // Increment the depth for every '-' character encountered
23 currentDepth++;
24 } else {
25 // Calculate the node's value
26 currentValue = 10 * currentValue + (traversal[i] - '0');
27 }
28
29 // Check for end of number or end of string
30 if (i + 1 == traversal.length() || (isdigit(traversal[i]) && traversal[i + 1] == '-')) {
31 TreeNode* newNode = new TreeNode(currentValue);
32
33 // If the stack size is greater than the current depth, pop until the sizes match
34 while (nodesStack.size() > currentDepth) {
35 nodesStack.pop();
36 }
37
38 // If stack is not empty, assign the newNode to the appropriate child of the top node
39 if (!nodesStack.empty()) {
40 if (nodesStack.top()->left == nullptr) {
41 nodesStack.top()->left = newNode;
42 } else {
43 nodesStack.top()->right = newNode;
44 }
45 }
46
47 // Push the new node onto the stack
48 nodesStack.push(newNode);
49
50 // Reset current depth and value for the next node
51 currentDepth = 0;
52 currentValue = 0;
53 }
54 }
55
56 // The result is the root of the tree. It's the bottommost node in the stack.
57 TreeNode* result = nullptr;
58 while (!nodesStack.empty()) {
59 result = nodesStack.top();
60 nodesStack.pop();
61 }
62
63 // Return the recovered binary tree
64 return result;
65 }
66};
671// Definition for a binary tree node
2class TreeNode {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6
7 constructor(val: number) {
8 this.val = val;
9 this.left = null;
10 this.right = null;
11 }
12}
13
14// Function to recover a tree from a given preorder traversal string
15function recoverFromPreorder(traversal: string): TreeNode | null {
16 let nodesStack: TreeNode[] = [];
17 let currentDepth = 0;
18 let currentValue = 0;
19
20 for (let i = 0; i < traversal.length; ++i) {
21 if (traversal[i] === '-') {
22 // Increment the depth for every '-' character encountered
23 currentDepth++;
24 } else {
25 // Calculate the node's value
26 currentValue = 10 * currentValue + parseInt(traversal[i]);
27 }
28
29 // Check for end of number or end of string
30 if (i + 1 === traversal.length || (traversal[i] !== '-' && traversal[i + 1] === '-')) {
31 let newNode = new TreeNode(currentValue);
32
33 // If the stack size is greater than the current depth, pop until the sizes match
34 while (nodesStack.length > currentDepth) {
35 nodesStack.pop();
36 }
37
38 // If stack is not empty, assign the newNode to the appropriate child of the top node
39 if (nodesStack.length > 0) {
40 if (nodesStack[nodesStack.length - 1].left === null) {
41 nodesStack[nodesStack.length - 1].left = newNode;
42 } else {
43 nodesStack[nodesStack.length - 1].right = newNode;
44 }
45 }
46
47 // Push the new node onto the stack
48 nodesStack.push(newNode);
49
50 // Reset current depth and value for the next node
51 currentDepth = 0;
52 currentValue = 0;
53 }
54 }
55
56 // The result is the root of the tree. It's the last node added to the stack.
57 while (nodesStack.length > 1) {
58 nodesStack.pop();
59 }
60
61 // We return the root of the binary tree which the stack should now contain
62 return nodesStack.length > 0 ? nodesStack[0] : null;
63}
64What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Time and Space Complexity
The given code traverses the string S once to reconstruct a binary tree from its preorder traversal description. The length of the string S is denoted as n.
Time Complexity
The time complexity depends on the number of operations performed as the string is being processed:
- Each character is visited once, which results in
O(n)time complexity for the traversal. - The stack operations (pushing and popping nodes) occur once for each node added to the tree. In the worst case, it's possible for every node to be pushed and then popped, but that is bounded by the number of nodes in the tree, and hence by
n. Therefore, stack operations contributeO(n)to time complexity.
Overall, the time complexity of the function is O(n).
Space Complexity
The space complexity primarily depends on the stack used to reconstruct the tree:
- The maximum size of the stack is determined by the maximum depth of the tree. In the worst case (a skewed tree), the depth can be
O(n)if each node except the last has only one child. Therefore, the stack can useO(n)space. - The space for the tree itself, if considered, would also be
O(n)since we are creating a new node for every value in the stringS.
Considering the stack and the space for the new tree nodes, the overall space complexity of the function is O(n).
Learn more about how to find time and space complexity quickly using problem constraints.
What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.