Given a binary tree, find out the minimum length sum path form root to leaf with sum S. What about finding minimum length sum path for BST? How does BST improve the search? For example, the min length path for sum S=13 in T1 is 2 (6–>7 not, 6–>4–>3). For T2 min length path for […]
Tag Archives: BST
Given a binary search tree. Find the kth smallest element in the BST. A quick solution would be to perform a modified inorder traversal with an extra parameter k. Each time inorder traversal is popping a node out of recursion/call stack (i.e. unwinding a recursion)then we keep decreasing the k. When k=0 then the current […]
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 […]
From wiki, A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all […]