Given the level order traversal of a Binary Search Tree, write an algorithm to construct the Binary Search Tree or BST from ITS given level order traversal. Example Input levelOrder[] = {18, 12, 20, 8, 15, 25, 5, 9, 22, 31} Output In-order : 5 8 9 12 15 18 …
Given a pre-order traversal of a Binary Search Tree(BST), write an algorithm to construct the BST from given preorder traversal. Examples Input preOrder[] = {7, 5, 3, 6, 9} Output Inorder : 3 5 6 7 9 Input preOrder[] = {12, 6, 1, 35, 20} Output Inorder : 1 6 …
In this problem we have given a Binary Search Tree, write an algorithm to convert best to a tree with sum of all smaller keys. Example Input Output Pre-order : 19 7 1 54 34 88 Naive Approach Traverse all the nodes one by one in any traversal form, and …
Given a Binary Search Tree, write an algorithm to find the node with the minimum value in a given binary search tree. Example Input Output 5 Naive Approach A simple approach is to do a tree traversal and find the node with the minimum value among all the nodes. This …
In reverse a path in BST using queue problem we have given a Binary Search Tree and node, write an algorithm to reverse the path from root to the given node. Assume that the node exists in the BST. Example Input Target Node = 12 Output In-order traversal before the …
In this problem, we have given a BST and a number k, find the kth smallest element in a BST. Examples Input tree[] = {5, 3, 6, 2, 4, null, null, 1} k = 3 Output 3 Input tree[] = {3, 1, 4, null, 2} k = 1 Output 1 …
Given the root of a binary search tree and two nodes n1 and n2, find the LCA(Lowest Common Ancestor) of the nodes in a given binary search tree. Example Naive Approach for Lowest Common Ancestor in Binary Search Tree Find the LCA(n1, n2) using the optimal approach to find LCA …
A binary search tree is a Binary tree with some rules that allows us to maintain the data in a sorted fashion. As it is a binary tree hence, a node can have at max 2 children. Structure of a Binary Search Tree node Rules for Binary tree to …
Consider a binary search tree, two nodes of the tree have been swapped, design an algorithm to recover the binary search Tree. Example Consider the binary search tree given below whose two nodes have been swapped as input. Incorrect nodes on the BST are detected(highlighted) and then swapped to obtain …
In Trim a Binary Search Tree problem we have given a binary search tree and a lower (as L) and higher bound (as R) of a range of integer values, trim the BST so that all its elements lie in the range[L,R] (R >= L). If the given BST root …