Tag Archives: bst interview questions

Binary Search Trees from keys 1 to n

Construct Binary Search Trees from keys 1 to n Problem statement to construct a Binary Search Tree(BST) from keys 1 to n. We are given a list of consecutive numbers from 1 to . Determine the number of binary trees that can be constructed from these numbers. Example for building a Binary Search Tree from keys… Read More »

Sorted Linked List to balanced Binary Search Tree

Sorted Linked List to balanced Binary Search Tree (BST). Problem statement to create a Binary Search Tree from a sorted linked list. Given a singly linked list in a sorted order, create a balanced binary search tree (BST). Example: INPUT: Linked List: 1->5->8->10->12->15->20 OUTUT: 10 / \ 5 15 / \ / \ 1 8 12 20 Create… Read More »

Print common nodes in two Binary Search Trees

Print common nodes in two Binary Search Trees Problem statement to print common nodes in two Binary Search Trees (BST). Given two binary search trees, print all the elements that are common in both the trees. Example: INPUT:Tree 1 10 / \ 5 15 / \ / \ 1 8 12 20 Tree 2 7… Read More »

Create a BST such that sum of all greater keys is added to its every key

Create a BST such  that sum of all greater keys is added to its every key. Problem statement to construct a Binary Search Tree (BST) such  that sum of all greater keys is added to its every key: Given a balanced binary search tree (BST), build a binary search tree such that all nodes in original… Read More »

Check identical Binary Search Tree (BST)

Check identical Binary Search Tree (BST) without building a tree Problem statement to check identical Binary Search Tree (BSTs) without building a tree. We are given two arrays of integers from each of which we have to make a binary search tree(BST). We need to determine whether these binary search trees (BSTs) will be identical… Read More »

Remove Binary Search Tree keys outside a given range

Remove Binary Search Tree (BST) keys outside a given range Or Remove BST keys that don’t lie in given range/remove bina. Remove BST keys outside a given range Problem Statement: Given a Binary Search Tree(BST) and a range say [ k1 , k2 ], remove all the nodes, whose values lie outside the given range.… Read More »

Inorder Successor and Predecessor of a given Key in BST

Inorder Successor and Predecessor of a given Key in Binary Search Tree (BST) Inorder Successor and Predecessor of a given Key in BST Problem Statement: Given a Binary Search Tree (BST) and a key, you need to tell the values will precede and succeed the given key in the Inorder Traversal. If the given key… Read More »

Convert BST to Greater Sum Tree

Convert BST to Greater Sum Tree This problem can also be stated as BST to Binary Tree Conversion with data of nodes as the sum of all greater elements. This program/question can be seen as an extension/ modification of converting BST to Binary Tree with data of nodes as sum of all greater value nodes.… Read More »

Add all greater values to each node in BST

Add all greater values to each node in Binary Search Tree (BST) This problem can also be stated as BST to Binary Tree Conversion with data of nodes as the sum of all greater elements plus the original value of the node. Add all greater values to each node in BST Problem Statement: Given a… Read More »

Sorted Array to Balanced BST

Sorted Array to Balanced Binary Search Tree (BST) Given a sorted array convert it to a balanced Binary Search Tree (BST). Sorted Array to Balanced BST Example: Input: Array {1, 2, 5} Output: A Balanced BST 2 / \ 1 5 Input: Array {1, 2, 3, 4, 5} Output: A Balanced BST 3 / \… Read More »