Check Postordered Array Forms a BST - Algorithms and Problem SolvingAlgorithms and Problem Solving

Check Postordered Array Forms a BST - Algorithms and Problem SolvingAlgorithms and Problem Solving

Posted on Given an array that contains a Post order traversal of a Binary Tree. Check if a possible Binary Tree formed from the postorder traversal is a Binary Search Tree. For example, a1=[1, 3, 4, 2, 7, 6, 5] is a BST but a2=[1, 3, 4, 6, 7, 2, 5] is not a BST. 5 5 / \ / \ 2 6 4 2 / \ \ / \ 1 4 7 3 7 / / / 3 1 6 (a1) (a2) In order to be a BST, a binary tree should satisfy that any subtree rooted at node r is greater than all nodes in its left subtree and smaller than nodes in its right subtree. Now, in post order traversal we traverse left subtree first then the right subtree and at last the root. Thus, if the array is a post traversal of a BST, then a[0..n-1] can be divided into two parts a[0..i-1] and a[i, n-2],

Read full article from Check Postordered Array Forms a BST - Algorithms and Problem SolvingAlgorithms and Problem Solving