Problem

We run a preorder depth-first search (DFS) on the root of a binary tree.

At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node.  If the depth of a node is D, the depth of its immediate child is D + 1.  The depth of the root node is 0.

If a node has only one child, that child is guaranteed to be the left child.

Given the output traversal of this traversal, recover the tree and return its root.

Examples

Example 1:

graph TD;
	A("1")
	B("2")
	C("3")
	D("4")
	E("5")
	F("6")
	G("7")
	
	A --- B & E
	B --- C & D
	E --- F & G
  
1
2

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

Example 2:

graph TD;
	A("1")
	B("2")
	C("3")
	D("4")
	E("5")
	F("6")
	G("7")
	
	A --- B & E
	B --- C
	B ~~~ N1:::hidden
	C --- D
	C ~~~ N2:::hidden
	
	E --- F
	E ~~~ N3:::hidden
	F --- G
	F ~~~ N4:::hidden


classDef hidden display: none;
  
1
2

Input: traversal = "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]

Example 3:

graph TD;
	A("1")
	B("401")
	C("349")
	D("88")
	E("90")
	
	A --- B
	A ~~~ N1:::hidden
	B --- C & D
	C --- E
	C ~~~ N2:::hidden


classDef hidden display: none;
  
1
2

Input: traversal = "1-401--349---90--88"
Output: [1,401,null,349,88,90]

Constraints:

  • The number of nodes in the original tree is in the range [1, 1000].
  • 1 <= Node.val <= 10^9

Solution

Method 1 - Iterative using stack

Here is the approach:

  1. Parse the string to extract (depth, value) pair. This helps us extract numbers and their corresponding depths based on the count of dashes.
  2. Initialise an empty stack to keep track of nodes at each depth. This helps in identifying where to attach a node in the tree (as the child of which parent node).
  3. For each extracted (depth, value):
    • Create a tree node with the given value.
    • If the stack’s size corresponds to the depth, attach this node as a left child of the last node in the stack.
    • Otherwise, pop nodes from the stack until the stack’s size matches the current depth, and then attach the node as the right child of the last node in the stack.
    • Add the current node to the stack.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    public TreeNode recoverFromPreorder(String traversal) {
        Deque<TreeNode> stk = new ArrayDeque<>();
        int i = 0, n = traversal.length();
        
        while (i < n) {
            int d = 0;
            // Count depth (number of dashes)
            while (i < n && traversal.charAt(i) == '-') {
                d++;
                i++;
            }
            
            // Read value of node
            int val = 0;
            while (i < n && Character.isDigit(traversal.charAt(i))) {
                val = val * 10 + (traversal.charAt(i) - '0');
                i++;
            }
            
            TreeNode cur = new TreeNode(val);
            // Adjust stack size to current depth
            while (stk.size() > d) stk.pop();

            if (!stk.isEmpty()) {
                if (stk.peek().left == null) {
	                stk.peek().left = cur;
	            }
                else {
	                stk.peek().right = cur;
	            }
            }
            
            stk.push(cur);
        }
        
        // The root node remains in the bottom of the stack
        return stk.isEmpty() ? null : stk.getLast();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
        stk: list[TreeNode] = []
        i, n = 0, len(traversal)
        
        while i < n:
            d = 0
            # Count depth (number of dashes)
            while i < n and traversal[i] == '-':
                d += 1
                i += 1
            
            # Read value of node
            val = 0
            while i < n and traversal[i].isdigit():
                val = val * 10 + int(traversal[i])
                i += 1
            
            cur = TreeNode(val)
            # Adjust stack size to current depth
            while len(stk) > d:
                stk.pop()
            
            if stk:
                if stk[-1].left is None:
                    stk[-1].left = cur
                else:
                    stk[-1].right = cur
            
            stk.append(cur)
        
        # The root node remains in the bottom of the stack
        return stk[0] if stk else None

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. Parsing the string and processing each node takes O(n).
  • 🧺 Space complexity: O(h), , where h is the height of the tree. The maximum depth of the stack is O(h)