Search code examples
c++binary-treeinorderpostorderpreorder

Finding the other two traversals of a Binary Tree when given only one traversal

I know you can reconstruct a binary tree when given its inorder and preorder traversals as strings, but is it possible to find the postorder and/or preoder traversals when only given the inorder traversal?

Solution

  • No, retrieving postorder/preorder from only inorder traversal is not possible. If it was, it would be possible to reconstruct a binary tree with only the inorder traversal, which is not possible because one inorder traversal can give you several possible reconstructed binary trees.