Non-recursive algorithm to find the pre-order successor of a given node in a BST

Question: Write a non-recursive algorithm to find the pre-order successor of a given node in a BST. Solution: Let me tell you the background first. There are basically three kind of traversal for a binary tree. Each traversal is named on the basis of processing of root node. For example in preorder traversal, root will […]

Convert a binary search tree to sorted list

Ques: You have given a binary search tree and you need to change this tree to link list that contains nodes in sorted order. Solution: We all know that smaller values are on left side. So we need to keep left side values at first place for sorted list. To make this happen we will […]

Height of the binary tree stored in array.

Qus: A binary tree is stored in an array( a) such that a[i] is the parent of i. Suppose an element in array is 6, the parent of this element will be a[6]. The parent of the root is -1. It is not a binary search tree. Find the height of the tree. Solution: Let’s […]

Find height of a binary tree iteratively.

To solve this kind of problem, first try to figure out how would you solve if it is given on copy in pictorial format. Let say a tree is given as given below and we need to calculate the height of the tree, how would you do that? It is as simple as that, we […]

How to create binary search tree?

Most of the people already know the algorithm to create a binary search tree. The basic idea is to insert new value in existing binary search tree. What if the given binary search tree doesn’t exist means it is null? We will create a node with the given value and that will be the root […]