Tag Archive | amazon interview question

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

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