1028. Recover a Tree From Preorder Traversal LeetCode Solution

In this guide, you will get 1028. Recover a Tree From Preorder Traversal LeetCode Solution with the best time and space complexity. The solution to Recover a Tree From Preorder Traversal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Recover a Tree From Preorder Traversal solution in C++
Recover a Tree From Preorder Traversal solution in Java
Recover a Tree From Preorder Traversal solution in Python
Additional Resources

1028. Recover a Tree From Preorder Traversal LeetCode Solution image

Problem Statement of Recover a Tree From Preorder Traversal

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h)

1028. Recover a Tree From Preorder Traversal LeetCode Solution in C++

class Solution {
 public:
  TreeNode* recoverFromPreorder(string traversal) {
    int i = 0;
    return recoverFromPreorder(traversal, 0, i);
  }

 private:
  TreeNode* recoverFromPreorder(const string& traversal, int depth, int& i) {
    int nDashes = 0;
    while (i + nDashes < traversal.length() && traversal[i + nDashes] == '-')
      ++nDashes;
    if (nDashes != depth)
      return nullptr;

    i += depth;
    const int start = i;
    while (i < traversal.length() && isdigit(traversal[i]))
      ++i;

    return new TreeNode(stoi(traversal.substr(start, i - start)),
                        recoverFromPreorder(traversal, depth + 1, i),
                        recoverFromPreorder(traversal, depth + 1, i));
  }
};
/* code provided by PROGIEZ */

1028. Recover a Tree From Preorder Traversal LeetCode Solution in Java

class Solution {
  public TreeNode recoverFromPreorder(String traversal) {
    return recoverFromPreorder(traversal, 0);
  }

  private int i = 0;

  private TreeNode recoverFromPreorder(final String traversal, int depth) {
    int nDashes = 0;
    while (i + nDashes < traversal.length() && traversal.charAt(i + nDashes) == '-')
      ++nDashes;
    if (nDashes != depth)
      return null;

    i += depth;
    final int start = i;
    while (i < traversal.length() && Character.isDigit(traversal.charAt(i)))
      ++i;

    return new TreeNode(Integer.valueOf(traversal.substring(start, i)),
                        recoverFromPreorder(traversal, depth + 1),
                        recoverFromPreorder(traversal, depth + 1));
  }
}
// code provided by PROGIEZ

1028. Recover a Tree From Preorder Traversal LeetCode Solution in Python

class Solution:
  def recoverFromPreorder(self, traversal: str) -> TreeNode | None:
    i = 0

    def recoverFromPreorder(depth: int) -> TreeNode | None:
      nonlocal i
      nDashes = 0
      while i + nDashes < len(traversal) and traversal[i + nDashes] == '-':
        nDashes += 1
      if nDashes != depth:
        return None

      i += depth
      start = i
      while i < len(traversal) and traversal[i].isdigit():
        i += 1

      return TreeNode(int(traversal[start:i]),
                      recoverFromPreorder(depth + 1),
                      recoverFromPreorder(depth + 1))

    return recoverFromPreorder(0)
 # code by PROGIEZ