2
$\begingroup$

I have tried to solve and understand LeetCode question "297. Serialize and Deserialize Binary Tree", and after I read their solution I came up with a question that I will be glad If you can help me to understand. First of all, two binary trees with different structures can have the same preorder result and that is the first problem in the leetcode solution they are going to solve.

Tree one (T1):

      a
     / 
    b   

Preorder result = [a,b]

Tree two (T2):

      a
       \
        b

Preorder result = [a,b]

T1 != T2 but they have the same preorder result as you can see above.

Now when they (leetcode) do preorder search they append nulls values ("N") to the result and that solves this problem such that every two different trees must have different result. But I don't understand why this is happening and how can I prove it mathematically that all two different trees must have different preorder result after this change? (Example bellow)

Tree one (T1):

      a
     / \
    b   N
   / \
  N   N

preorder result = [a,b,N,N,N]

Tree two (T2):

        a
       / \
      N   b
         / \
        N   N

preorder result = [a,N,b,N,N]

More Info about this trick can be found in the Cracking the Coding Interview book on page 265:

enter image description here

$\endgroup$
0
0
$\begingroup$

When we change each non-existent child of each leaf node into a special node , a binary tree becomes a full Binary tree with distinguished leaf nodes.

  • A full binary tree is a special type of binary tree in which every node has either two or no children. For example, the logo/favicon of this site is a full binary tree!
  • A distinguish leaf node means a node that its value or its representation (as recorded in a tree traversal) alone tells that it is a leaf node. For example, the nodes with value "N" as in LeetCode or the nodes that are represented by a special character "X" in the Cracking the Coding Interview book. (Once those non-existent nodes or NULL nodes are represented or stored, we consider them as real nodes in the corresponding full binary tree.)

For example, the binary tree T1 of two nodes in the question becomes a full binary tree of five nodes, which is also denote T1 in the question. Note that each node in the first T1 becomes an internal node in the second T1 while each non-existent child node in the first T1 becomes a distinguished leaf node in the second T1.


Claim 1. The number of leaves in a full binary tree is one more than the number of its internal nodes.
Proof. We can obtain any full binary tree by growing the single-node tree step by step, each step adding two children to a leaf node.

For example, in one step we can grow

      a
     / \
    b   c

to

      a
     / \
    b   c
   / \
  d   e

or

      a
     / \
    b   c
       / \
      d   e

So in each step, one leaf node becomes internal node and two new leaf nodes are added. In other words, we have one more internal node and one more leaf node. So the difference between the number of internal nodes and the number of leaf nodes does not change. Since that difference for the initial single-node tree is 1, it stays at 1 forever. $\checkmark$

In fact, if that difference for an arbitrary binary tree is 1, then that binary tree must be a full binary tree. This fact will not be used here, however.


Corollary 2. If we traverse a full binary tree in preorder, then the leaf nodes visited so far are always no more than internal nodes visited so far at each step, except at the end of the traversal when leaf nodes are one more than than the internal nodes.
Proof: Use induction since each subtree of a full binary tree is also a full binary tree. Detail is left as an exercise. $\checkmark$


Corollary 3. Let $F$ be a full binary tree with distinguished leaf nodes. Let $[u_0, u_1, \cdots, u_{n-1}]$ be the preorder traversal of $F$, where $n\ge3$ is the number of nodes in $F$. Scanning that list of nodes from left to right, let $d$ be the first index when we have scanned the same number of leaf nodes as the number of internal nodes. Then

  • $[u_1, \cdots, u_d]$ is the preorder traversal of the left subtree of $F$ and
  • $[u_{d+1}, \cdots, u_{n-1}]$ is the preorder traversal of the right subtree of $F$.

Proof. Since leaf nodes are distinguished, we know whether each node is a leaf node or an internal node by looking at its value/representation in that list. This corollary follows from Corollary 2, noting that the first node visited, $u_0$, the root node is an internal node. $\checkmark$


Claim 4. A full binary tree with distinguished leaf nodes is determined uniquely by the result of its preorder traversal.
Proof.

  • Sure if the unknown full binary tree is a single-node tree.
  • Otherwise, Corollary 3 shows that we can recover the unknown full binary tree recursively given its preorder traversal. $\checkmark$

What LeetCode or Cracking the Coding Interview book does is expanding a given binary tree into a full binary tree by changing the non-existent children as distinguished leaf nodes. Given a preorder traversal of that full binary tree with distinguished leaf nodes, we can recover that full binary tree, thanks to Claim 4. From that full binary tree, we can recover the given binary tree by removing all leaf nodes.

Since we can recover the given binary tree from the preorder traversal of its corresponding full binary tree, different binary trees must lead to different preorder traversal of their corresponding full binary trees.


Exercise 1. What happens to the postorder traversal of a binary tree?

Exercise 2. What happens to the inorder traversal of a binary tree?

$\endgroup$
2
  • $\begingroup$ Here is another way to prove Claim I. Let $nl, ni$ be the number of the left nodes and the internal nodes, respectively. Then $2ni = ni + nl - 1$ since $2ni$ is the number of edges and $ni+nl$ is the number of nodes. So $ni = nl - 1$. $\endgroup$
    – John L.
    Oct 9 at 3:39
  • $\begingroup$ This answer does not explain directly why the top-voted solutions on LeetCode such as Easy to understand Java Solution or Recursive preorder, Python and C++, O(n) works. $\endgroup$
    – John L.
    Oct 14 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.