Tag Archives: Data structures

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 »

Construct an array from it’s pair sum array

Construct an array from it’s pair sum array In this post we deal with the problem of constructing the original array from the array in which the sum of all pairs that can be made from the input array are given. Construct an array from it’s pair sum array Problem Statement: Given a pair-sum array… Read More »

Remove duplicates in a Binary Search Tree

Remove duplicate nodes in a Binary Search Tree (BST). Problem statement to remove redundant nodes in a Binary Search Tree. Given a binary search tree (BST), remove the redundant nodes to obtain a tree without the duplicate elements. Example: INPUT: array: 1,5,8,10,10,12,15,20,20,20 OUTUT: 10(2) / \ 5 15 / \ / \ 1 8 12 20(3)… 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 »

Second largest element in Binary Search Tree

Second largest element in Binary Search Tree (BST). Problem statement to find the second largest element in a Binary Search Tree (BST) Given a binary search tree, determine its second largest element. In inorder traversal, the second last element is the second largest while in reverse inorder traversal, the second element is second largest element. Example:… 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 »

Binary Search Tree from preorder traversal

Binary Search Tree from preorder traversal. Problem statement to create a Binary Search Tree from a preorder traversal Given only a preorder traversal of a binary search tree (BST), create a tree. Example: INPUT:array= {10, 5, 1, 8, 12, 15, 20} OUTUT: 10 / \ 5 15 / \ / \ 1 8 12 20 Create a… Read More »

Triplets in a Binary Search Tree that sum to zero

Triplets in a Binary Search Tree that sum to zero. Problem statement to find three numbers in a binary search tree that sum to zero: Given a balanced binary search tree (BST), determine if there exist three numbers that add up to zero.If they exist, output YES. Example for testing if 3 numbers in a BST… Read More »

Check internal node of Binary Search Tree for exactly one child

Check internal node of Binary Search Tree for exactly one child. Problem statement to check internal node of Binary Search Tree for exactly one child: Given a preorder traversal of a binary search tree (BST), determine if each internal (non-leaf) node has exactly one child. Example for testing if each internal node of a Binary Search Tree (BST) has only one… Read More »