Tag Archives: bst

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 »

Check if a Binary Tree is BST or not

Check if a Binary Tree is BST or not Given a Binary Tree, we need to print the level of a given data/node in the Binary Tree, or print a statement to tell it is absent from the tree in case it is not present. Check if a Binary Tree is BST or not Example:… Read More »

Size of a Binary Tree

Size of a Binary Tree Given a binary tree, we need to print the size of the Binary tree, i.e. the number of nodes present in it. Example: Given this Binay Tree as input: 80 / \ 60 110 / \ / \ 35 40 85 130 For this tree shown above the answer should… Read More »

Print BST keys in the given range.

Print Data of nodes of BST in the given range. Given two values low and high (where low < high) and pointer to the root of a Binary Search Tree. We need to print all the keys of tree in range low to high. i.e. print all x such that low<=x<=high and x is a… Read More »

Deletion from a Binary Search Tree

Deletion from a Binary Search Tree (BST). While deleting there can be 3 cases that arise: Case 1: The node to be deleted is a leaf node : Delete it directly. 80 80 / \ / \ 60 110 Delete (35)>>> 60 110 / \ / \ \ / \ 35 40 85 130 40… Read More »

Minimum Value in a Binary Search Tree

Finding Minimum Value in a Binary Search Tree(BST). Given a Binary Search Tree(BST) we need to find the minimum value in it. 80 / \ 60 110 / \ / \ 35 40 85 130 Solution (is very simple): Keep on traversing the left node from root recursively. The node whose left  is null, is the answer.35… Read More »