Tag Archive | algorithm

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 […]

Sub-array with sum zero

Ques: An array contains negative as well as positive numbers in random order, find the first sub array for which the sum of all the elements is zero. Solution: First of all we need to think how can we find out if the sum of all the elements in a sub array is zero. Let’s […]

Find the loop in a given Link List. Analyze the complexity of solution.

Link list is one of those data structures on which you can find a lot of stuff on internet. From a very simple problem to a complex one. Here in this blog also we are going to discuss problems along the same line. Continuing in the same direction, let’s discuss our first problem. Suppose you […]

What is stack? How to implement it?

Most of us already know that Stack is a data structure which allow us to process data in a particular manner called Last in First out, which means that the data stored last will be processed first. For an example if we have to store data 1 2 3 4 5, 1 will be in […]

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 […]