1028. Recover a Tree From Preorder Traversal

[mah-shamim]

Discussed in #1346

^{Originally posted by mah-shamim February 23, 2025}
Topics: String, Tree, Depth-First Search, Binary Tree

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.

Example 1:

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

Example 2:

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

Example 3:

• 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 <= 109

Hint:

1. Do an iterative depth first search, parsing dashes from the string to inform you how to link the nodes together.

[mah-shamim]

We need to reconstruct a binary tree from its preorder traversal string where each node's depth is indicated by the number of dashes preceding its value. The challenge is to correctly parse the string and build the tree according to the preorder traversal rules, ensuring that each node with a single child has it as the left child.

Approach

1. Parsing the Input String: The input string is parsed into a list of nodes, where each node is represented by its value and depth. This is done by iterating through the string, counting dashes to determine depth, and then reading the numerical value that follows.
2. Tree Construction: Using a stack-based approach, we iteratively build the tree. The stack helps track the current path from the root to the current node. For each node in the parsed list, we find its parent by popping elements from the stack until we reach the parent's depth. The node is then added as the left or right child of the parent, ensuring that left children are prioritized as per the problem constraints.

Let's implement this solution in PHP: 1028. Recover a Tree From Preorder Traversal

<?php
/**
 * @param String $traversal
 * @return TreeNode
 */
function recoverFromPreorder($traversal) {
    $nodes = parseNodes($traversal);
    if (empty($nodes)) return null;

    $root = new TreeNode($nodes[0][0]);
    $stack = array();
    array_push($stack, array($root, $nodes[0][1]));

    $n = count($nodes);
    for ($i = 1; $i < $n; $i++) {
        $val = $nodes[$i][0];
        $depth = $nodes[$i][1];

        // Pop stack until parent's depth is found
        while (end($stack)[1] != $depth - 1) {
            array_pop($stack);
        }
        $parentPair = end($stack);
        $parentNode = $parentPair[0];

        $newNode = new TreeNode($val);
        if ($parentNode->left === null) {
            $parentNode->left = $newNode;
        } else {
            $parentNode->right = $newNode;
        }
        array_push($stack, array($newNode, $depth));
    }

    return $root;
}

/**
 * @param $traversal
 * @return array
 */
function parseNodes($traversal) {
    $nodes = array();
    $i = 0;
    $n = strlen($traversal);
    while ($i < $n) {
        // Count dashes
        $dashCount = 0;
        while ($i < $n && $traversal[$i] == '-') {
            $dashCount++;
            $i++;
        }
        // Read number
        $num = 0;
        while ($i < $n && is_numeric($traversal[$i])) {
            $num = $num * 10 + intval($traversal[$i]);
            $i++;
        }
        array_push($nodes, array($num, $dashCount));
    }
    return $nodes;
}

// Test cases
$traversal1 = "1-2--3--4-5--6--7";
$traversal2 = "1-2--3---4-5--6---7";
$traversal3 = "1-401--349---90--88";

print_r(recoverFromPreorder($traversal1)); //Output: [1,2,5,3,4,6,7]
print_r(recoverFromPreorder($traversal2)); //Output: [1,2,5,3,null,6,null,4,null,7]
print_r(recoverFromPreorder($traversal3)); //Output: [1,401,null,349,88,90]
?>

Explanation:

1. Parsing the Input String: The parseNodes function converts the input string into a list of tuples, each containing a node's value and its depth. This is done by iterating through the string, counting dashes for depth, and then reading the numerical value.
2. Tree Construction: The recoverFromPreorder function initializes the root node and uses a stack to keep track of nodes as we build the tree. For each subsequent node, we find its parent by adjusting the stack to the correct depth. The node is then added as the left child if possible, otherwise as the right child. This ensures the tree structure adheres to the preorder traversal and problem constraints.