Binary Tree with In-Order and Pre-order Path

Question

I’m having some doubts about the route taken by this binary tree:

1. Could you classify it as binary? Since it has 3-leaf knots?

   T=(35,(80,(7,(11,(12)),(15,(6,(0),(1),(2)),(9))),(3,(18),(8))),(73,(13),(27),(61)))
   

2. Would it be correct to state that the courses are these?

   Pre-order:

   35,80,7,11,12,15,6,0,1,2,9,3,18,8,73,13,27,71
   

   In-Order:

   12,11,0,1,2,6,9,15,7,18,8,3,80,35,13,27,71,73
   

Answer 1

In that notation, a sequence of the type (A,(B),(C)) means that A is a knot that has as children the subtrees B and C.

Let’s draw this tree:

1. In a binary tree, no node can have more than two children. The (6,(0),(1),(2)) and the (73,(13),(27),(61)) who are there in the middle are clearly violations of that, by representing us with three children. Node 11 has no right child, only the left.

2. The search in pre-order consists in visiting each node, first visiting the number contained in it and then the subtree on the left and finally the one on the right. Recursively. In case there are more than two children, they should be visited from left to right. The notation given (A,(B),(C)) will already represent the tree in preorder, and therefore the result of the visit of the nodes will be the same sequence in which they appear in that notation, no matter where they are in the tree. So the result is then: 35, 80, 7, 11, 12, 15, 6, 0, 1, 2, 9, 3, 18, 8, 73, 13, 27 and 61. Your answer is almost correct, the only detail is that the last number is 61 instead of 71.

3. The in-order search consists of visiting each node, first visiting the left child, then the knot itself, and then the right child. Recursively. Consists of replacing (A,(B),(C)) for ((B),A,(C)).

   In the case of a knot (A,(B),(C),(D)) who has more than two children, it is not clear what should be done, since the in-order visit is only defined for cases where there are no more than two children. There are two possibilities here: replace (A,(B),(C),(D)) for ((B),A,(C),(D)) or by ((B),(C),A,(D)). That means that the (6,(0),(1),(2)) could be visited as 0, 6, 1, 2 or as 0, 1, 6, 2.

   The resulting order would be 12, 11, 7, 0, [1 and 6], 2, 15, 9, 80, 18, 3, 8, 35, 13, [73 and 27], 61. Numbers in [A and B] format can be exchanged depending on whether you want to use ((B),A,(C),(D)) or ((B),(C),A,(D)).

   What you seem to be wanting is the view on post-order which is to visit the node only after the children are visited. They consist of exchanging (A,(B),(C)) for ((B),(C),A). This ordination produces a result similar to what you proposed, only with the 35 at the end and with 61 at the place of 71. The post-order visit would be 12, 11, 0, 1, 2, 6, 9, 15, 7, 18, 8, 3, 80, 13, 27, 61, 73 and 35.

One way to understand the ordering is to see the diagram below:

The visits take place on the path of the sequence indicated by the arrows, skirting the tree. In this path, each node can be visited from the left, the bottom or the right. The arrows that arrive at the nodes from the left are the green ones, the ones that arrive from below are the yellow ones and the ones that arrive from the right are the red ones.

If you only consider the green arrows, you will be visiting in pre-order. If you only consider the yellow arrows, you will be making the visit in-order. If you only consider the red ones, you’re doing it in post-order.

Note that in the case of the in-order visit, the same node is accessed more than once below if there are more than two children (in this case, 6 and 73), since this situation is ambiguous in this circumstance.