1028. Recover a Tree From Preorder Traversal

HardTreeDepth-First SearchStringBinary Tree

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.

Flowchart Walkthrough

Let's analyze the problem from LeetCode 1028, "Recover a Tree From Preorder Traversal," using the algorithm flowchart here. We will step through the decision-making process to find the appropriate algorithm:

Is it a graph?

No, this problem explicitly involves a tree, which is a specific type of graph with certain properties (acyclic connected graph).

Is it a tree?

Yes: The whole task is to reconstruct a tree based on its preorder traversal.

Is the problem related to directed acyclic graphs (DAGs)?

No: Although a tree is technically a directed acyclic graph, the question is focused specifically on tree properties rather than general DAG properties. The challenge is to construct the tree, not work with DAG operations.

The flowchart suggests using DFS as the primary strategy for solving tree problems when it is not related to DAG-specific concerns. Depth-First Search (DFS) is an excellent fit for reconstructing a tree from traversal data, as it naturally follows the order of construction from the traversal sequence, mimicking the excavation of the tree structure step-by-step.

Therefore:

Conclusion: The flowchart and exploration of the problem suggest using the Depth-First Search (DFS) pattern to effectively reconstruct the tree from the given preorder traversal.

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.

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 st to 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 variables depth and num to store the current depth and the value of the node being processed, respectively.
Iterate through each character i in the given string S. If the current character is a dash '-', increment the depth counter depth. If the current character is a digit, update the node value num by 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 S is reached or the next character is a dash), a node needs to be created with the accumulated num value. This is done as follows:
- Create a new tree node newNode with the value num.
- Modify the stack to correspond to the proper depth by popping nodes until st.size() equals the current depth. This ensures that the top of the stack is the parent node of newNode.
- If the stack is not empty, attach newNode as a left child if the top node's left child is nullptr, otherwise as a right child. This aligns with the rule that singly childed nodes are left children.
- Push newNode onto 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.
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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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 is 1, we create the node with the value 2, and since the stack's current depth is also 1, this node is a left child of the top node on the stack. Attach node 2 as a left child of node 1 and push node 2 onto the stack.
The following four characters indicate a node with value 3 and a depth of 2. We pop node 2 off the stack since its depth is more than 1, and add node 3 as the left child of the new top of the stack, which is node 2. Push node 3 onto the stack.
Similarly, for the next node with a depth of 2 and value 4, we pop node 3 off the stack and attach node 4 as the right child of node 2 (since the left child is already present). Push node 4 onto the stack.
Proceed with characters '-5--6--7'. We encounter node 5 with a depth of 1, pop nodes until the stack depth matches 1, and then attach node 5 as the right child of the root node 1. Push node 5 onto the stack.
Node 6 has a depth of 2, so we pop node 5 to match the depth. Since node 5 has no left child, we attach node 6 as the left child. Push node 6 onto the stack.
Lastly, we handle node 7, which also has a depth of 2. We pop node 6 and attach node 7 as the right child of node 5. After pushing node 7 onto 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:

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
54

1import 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}
69

1#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};
67

1// 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}
64

Time 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 contribute O(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 use O(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 string S.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don't know