0

In-order traversal: 24,17,32,18,51,11,26,39,43
Pre-order traversal: 11,32,24,17,51,18,43,26,39

The question asked to find which nodes belong on the right subtree of the root node. I am having trouble constructing the tree based on the 2 traversal methods..

Would greatly appreciate some help on this.

Aqua
  • 17
  • 4
  • Have a look at [this blog post](https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/). – Mushroomator Apr 03 '22 at 17:50
  • You can't, in general, determine the full tree from just one type of traversal. And your tree does not produce the pre-order traversal you started with. – Scott Hunter Apr 03 '22 at 17:52
  • I think you confuse binary tree with binary **search** tree. A search tree has an additional condition `left < root < right` which a binary tree does not have. – Mushroomator Apr 03 '22 at 17:56
  • Oh crap you're right I did not read the question clearly... Thanks for your help!! – Aqua Apr 03 '22 at 18:00
  • 1
    Ok the nodes which belong to the right subtree of the root node would be 43, 26, 39. Is this correct? – Aqua Apr 03 '22 at 18:07
  • Originally you determined that the root was 11; do you still believe that, and if not, what do you think the root is now? – Scott Hunter Apr 03 '22 at 18:21
  • I still think root is 11 since pre order starts with root – Aqua Apr 04 '22 at 01:44
  • Why is this tagged with `binary-search` and `binary-search-tree`? – trincot Apr 04 '22 at 04:23

1 Answers1

0

The tree that is defined by those two traversals is:

        __ 11 __
       /        \
   _ 32 _        43
  /      \      /
24        51  26
  \      /      \
   17  18        39

The procedure to build this, is described in this Q&A

trincot
  • 317,000
  • 35
  • 244
  • 286