-1
$\begingroup$

I got this as the post order sequence but the answer says it is wrong. I do get a bit confused with the post order logic as well.

8 11 10 9 13 16 18 15

enter image description here

$\endgroup$
  • 1
    $\begingroup$ 13 should be the last node visited. The order is (left subtree), (right subtree), (root). You are not exploring 13's right subtree first. $\endgroup$ – ryan Sep 29 '19 at 20:25
  • $\begingroup$ I realised there are two 13's in the tree and I miseed one out in my sequence, so it would be 8 11 10 9 13 16 18 15 13? $\endgroup$ – Holz Sep 29 '19 at 21:03
  • $\begingroup$ Two nodes with the same key? If yes, then this is not classic BST $\endgroup$ – HEKTO Sep 29 '19 at 21:34
  • $\begingroup$ @Holz, yes. The sequence in your comment looks correct. $\endgroup$ – Steven Sep 29 '19 at 23:05
0
$\begingroup$

There are two 13 in the Binary Search Tree.

The left node of 15 can not be a 13 since it violates the BST property.

Instead, it can be replaced with 14 or any value in (13,15).

Resultant Traversal will be 8 11 10 9 x 16 18 15 13

where x is the value you choose to replace the left child of 15

$\endgroup$
0
$\begingroup$

The correct ordering is $8, 11, 10, 9, 13,16,18,15,13$

$\endgroup$

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.