Recover a Rooted Tree from Depth-Annotated Preorder

Question

The question asks the candidate to reconstruct a rooted tree from a given depth-annotated preorder traversal.

Codemia · Accepted Answer

To reconstruct a rooted tree from a depth-annotated preorder traversal, we can utilize a stack to keep track of the current nodes at different depths. We will iterate through the input list, using the depth information to determine when to create new child nodes or return to parent nodes.

1. Initialize an empty stack and a root node. 
2. For each entry in the depth-annotated list, check the depth. 
3. If the depth is greater than the stack size, create a new child node and push it onto the stack. 
4. If the depth is less than the stack size, pop nodes from the stack until the current depth is reached. 
5. Repeat until all nodes are processed.

The time complexity of this algorithm is O(n), where n is the number of nodes in the tree, as we process each node exactly once. The space complexity is O(h), where h is the height of the tree, due to the stack used for keeping track of the nodes.

```python
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

def recover_tree(preorder):
    root = TreeNode(preorder[0][1])
    stack = [root]
    for depth, value in preorder[1:]:
        node = TreeNode(value)
        if depth == len(stack):
            stack[-1].children.append(node)
        else:
            while len(stack) > depth:
                stack.pop()
            stack[-1].children.append(node)
        stack.append(node)
    return root
```

To ensure the solution works correctly, we can create test cases with various depth-annotated inputs and verify that the reconstructed tree matches the expected structure. For example, given the input `[(0, 'A'), (1, 'B'), (1, 'C'), (2, 'D')]`, the expected tree structure should have 'A' as the root, with 'B' and 'C' as children, and 'D' as a child of 'C'.

Recover a Rooted Tree from Depth-Annotated Preorder

Grammarly

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Grammarly Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string