For example, if the given sum is 66, there are two nodes in Figure 1 with value 25 and 41 whose sum is 66. While the given sum is 58, there are not two nodes whose sum is same as the given value.

Analysis: In a previous blog , we discussed how to check whether there are two numbers in a sorted array whose sum equals a given value. In order to solve this problem, we initialize a number num1 as the smallest number in the array, and initialize num2 as the greatest one. If the sum of num1 and num2 is same as the given value, two required numbers have been found. If the sum is greater than the given value, we move num2 to the previous number in the array (with less value). Similarly, we move num1 to the next number in the array (with greater value) if the sum is less than the given value.

Inspired by the solution, we may find two nodes with a given sum in a binary search tree with similar strategy. Firstly we initialize a pointer P1 to the smallest node in the tree, and another pointer P2 to the greatest node. When the sum of two values in the nodes pointed by P1 and P2 is same as the given value, two required nodes have been found. If their sum is greater than the given value, we move P2 to the previous node (containing less value). Moreover, we move P1 to the next node (containing greater value) if their sum is less than the given value.

It is not difficult to get the least and greatest value of a binary search tree. If we move along the links to left children, and the leaf node we arrive at finally contains the least value. For instance, if we move along the links to left children in Figure 1, the nodes on the path contain value 32, 24, 21 and 14, and 14 is the least value in the binary search tree.

Similarly, if we move along links to right children, and the leaf node we arrive at finally contains the greatest value.

The key to solve this problem is how to get the next nodes (with greater values) and the previous nodes (with less values) in a binary search tree. Let’s utilize stacks.

In order to get next nodes, we scan the tree along the links to leaf children, and push the scanned nodes into a stack. That’s to say, there are four nodes in the stack (nodes 32, 24, 21 and 14), and node 14 is on the top.

When the top of the stack is popped, node 21 on the top of stack is the next node of 14. And when the node 21 is popped, the node 24 on the top is the next node of 21.

The steps to get the next node of node 24 are more complex, because the node 24 has a right child. We pop the node 24, and push its right child, node 28, into the stack. And then, we scan the nodes from the right child along the links to left children. Therefore, the node 31 will also be pushed into the stack. At this time, there are three nodes in the stack (nodes 32, 28 and 25), and the top on the stack (node 25) is the next node of node 24.

Let’s summarize the steps to get next nodes. If the node on the top does not have a right child, the node is popped off, and the next node is on the top again. If the node on the top has a right child, after the node is popped off and then the right child is pushed, and all nodes along the links to left children are pushed into the stack. The last pushed node on the top is the next node. We continue the steps to pop and push until the stack is empty.

If you are interested, please try to analyze the steps to the next nodes after the node 25 by yourself.

The steps to get previous nodes are quite similar. At first we push the root node, and nodes along the links to right children. The node with least is on the top of stack. In order to get the previous nodes with less values, the top is popped off. If the top does not have a left child, the previous node is the new top node in the stack. If the top has the left child, we push its left child, as well as nodes along links to right children. The last pushed node is the previous node of the node popped.

Our solution can be implemented with the following C++ code:

bool hasTwoNodes(BinaryTreeNode* pRoot, int sum)

BinaryTreeNode* pNext = getNext(nextNodes);

if(currentSum < sum)

return false;

void buildNextNodes(BinaryTreeNode* pRoot, stack<BinaryTreeNode*>& nodes)

void buildPrevNodes(BinaryTreeNode* pRoot, stack<BinaryTreeNode*>& nodes)

BinaryTreeNode* getNext(stack<BinaryTreeNode*>& nodes)

BinaryTreeNode* pRight = pNext->m_pRight;

return pNext;

BinaryTreeNode* getPrev(stack<BinaryTreeNode*>& nodes)

BinaryTreeNode* pLeft = pPrev->m_pLeft;

return pPrev;

This solution costs O(n) time. The space complexity is O(height of tree), which is O(logn) on average, and O(n) in the worst cases.

Email This BlogThis! Share to X Share to Facebook Share to Pinterest

For instance, in the binary search tree in Figure 1, the node closest to 29 is the node with value 28.

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com , or Apress .

Email This BlogThis! Share to X Share to Facebook Share to Pinterest

Question: How to verify whether a binary tree is a binary search tree?

For example, the tree in Figure 1 is a binary search tree.

A node in binary tree is defined as:

struct BinaryTreeNode

{

int nValue;

BinaryTreeNode* pLeft;

BinaryTreeNode* pRight;

};

Analysis: Binary search tree is an important data structure. It has a specific character: Each node is greater than or equal to nodes in its left sub-tree, and less than or equal to nodes in its right sub-tree.

Solution 1: Verify value range of each node

If a binary search tree is scanned with pre-order traversal algorithm, the value in a root node is accessed to at first. After the root node is visited, it begins to scan nodes in the left sub-tree. The value of left sub-tree nodes should be less than or equal to the value of the root node. If value of a left sub-tree node is greater than the value of the root node, it violates the definition of binary search tree. It is similar for the right sub-tree.

Therefore, when it visits a node in binary search tree, it narrows the value range of left sub-tree and right sub-tree under the current visited node. All nodes are visited with the pre-order traversal algorithm, and their value is verified. If value in any node violates its corresponding range, it is not a binary search tree.

The following sample code is implemented based on this pre-order traversal solution:

bool isBST_Solution1(BinaryTreeNode* pRoot)

{

int min = numeric_limits<int>::min();

int max = numeric_limits<int>::max();

return isBSTCore_Solution1(pRoot, min, max);

}

bool isBSTCore_Solution1(BinaryTreeNode* pRoot, int min, int max)

{

if(pRoot == NULL)

return true;

if(pRoot->nValue < min || pRoot->nValue > max)

return false;

return isBSTCore_Solution1(pRoot->pLeft, min, pRoot->nValue)

&& isBSTCore_Solution1(pRoot->pRight, pRoot->nValue, max);

}

In the code above, value of each node should be in the range between min and max. The value of the current visited node is the maximal value of its left sub-tree, and the minimal value of its right sub-tree, so it updates the min and max arguments and verifies sub-trees recursively.

Solution 2: Increasing in-order traversal sequence

The first solution is based on pre-order traversal algorithm. Let us have another try on in-order traversal. The in-order traversal sequence of the binary search tree in Figure 1 is: 4, 6, 8, 10, 12, 14 and 16. It is noticeable that the sequence is increasingly sorted.

Therefore, a new solution is available: Nodes in a binary tree is scanned with in-order traversal, and compare value of each node against the value of the previously visited node. If the value of the previously visited node is greater than the value of current node, it breaks the definition of binary tree.

This solution might be implemented in C++ as the following code:

bool isBST_Solution2(BinaryTreeNode* pRoot)

{

int prev = numeric_limits<int>::min();

return isBSTCore_Solution2(pRoot, prev);

}

bool isBSTCore_Solution2(BinaryTreeNode* pRoot, int& prev)

{

if(pRoot == NULL)

return true;

return isBSTCore_Solution2(pRoot->pLeft, prev) // previous node

&& (pRoot->nValue >= prev) // current node

&& isBSTCore_Solution2(pRoot->pRight, prev = pRoot->nValue); // next node

}

The argument prev of the function isBSTCore_Solution2 above is the value of the previously visited node in pre_order traversal.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

Email This BlogThis! Share to X Share to Facebook Share to Pinterest

Question: How to get the median from a stream of numbers at any time? The median is middle value of numbers. If the count of numbers is even, the median is defined as the average value of the two numbers in middle.

Analysis: Since numbers come from a stream, the count of numbers is dynamic, and increases over time. If a data container is defined for the numbers from a stream, new numbers will be inserted into the container when they are deserialized. Let us find an appropriate data structure for such a data container.

An array is the simplest choice. The array should be sorted, because we are going to get its median. Even though it only costs O(lgn) time to find the position to be inserted with binary search algorithm, it costs O(n) time to insert a number into a sorted array, because O(n) numbers will be moved if there are n numbers in the array. It is very efficient to get the median, since it only takes O(1) time to access to a number in an array with an index.

A sorted list is another choice. It takes O(n) time to find the appropriate position to insert a new number. Additionally, the time to get the median can be optimized to O(1) if we define two pointers which points to the central one or two elements.

A better choice available is a binary search tree, because it only costs O(lgn) on average to insert a new node. However, the time complexity is O(n) for the worst cases, when numbers are inserted in sorted (increasingly or decreasingly) order. To get the median number from a binary search tree, auxiliary data to record the number of nodes of its sub-tree is necessary for each node. It also requires O(lgn) time to get the median node on overage, but O(n) time for the worst cases.

We may utilize a balanced binary search tree, AVL, to avoid the worst cases. Usually the balance factor of a node in AVL trees is the height difference between its right sub-tree and left sub-tree. We may modify a little bit here: Define the balance factor as the difference of number of nodes between its right sub-tree and left sub-tree. It costs O(lgn) time to insert a new node into an AVL, and O(1) time to get the median for all cases.

An AVL is efficient, but it is not implemented unfortunately in libraries of the most common programming languages. It is also very difficult for candidates to implement the left/right rotation of AVL trees in dozens of minutes during interview. Let us looks for better solutions.

As shown in Figure 1, if all numbers are sorted, the numbers which are related to the median are indexed by P1 and P2. If the count of numbers is odd, P1 and P2 point to the same central number. If the count is even, P1 and P2 point to two numbers in middle.

Median can be get or calculated with the numbers pointed by P1 are P2. It is noticeable that all numbers are divided into two parts. The numbers in the first half are less than the numbers in the second half. Moreover, the number indexed by P1 is the greatest number in the first half, and the number indexed by P2 is the least one in the second half.

Therefore, numbers in the first half are inserted into a max heap, and numbers in the second half are inserted into a min heap. It costs O(lgn) time to insert a number into a heap. Since the median can be get or calculated with the root of a min heap and a max heap, it only takes O(1) time.

Table 1 compares the solutions above with a sorted array, a sorted list, a binary search tree, an AVL tree, as well as a min heap and a max heap.

Table 1: Summary of solutions with a sorted array, a sorted list, a binary search tree, an AVL tree, as well as a min heap and a max heap.

Let us consider the implementation details. All numbers should be evenly divided into two parts, so the count of number in min heap and max heap should diff 1 at most. To achieve such a division, a new number is inserted into the min heap if the count of existing numbers is even; otherwise it is inserted into the max heap.

We also should make sure that the numbers in the max heap are less than the numbers in the min heap. Supposing the count of existing numbers is even, a new number will be inserted into the min heap. If the new number is less than some numbers in the max heap, it violates our rule that all numbers in the min heap should be greater than numbers in the min heap.

In such a case, we can insert the new number into the max heap first, and then pop the greatest number from the max heap, and push it into the min heap. Since the number pushed into the min heap is the former greatest number in the max heap, all numbers in the min heap are greater than numbers in the max heap with the newly inserted number.

The situation is similar when the count of existing numbers is odd and the new number to be inserted is greater than some numbers in the min heap. Please analyze the insertion process carefully by yourself.

The following is sample code in C++. Even though there are no types for heaps in STL, we can build heaps with vectors utilizing function push_heap and pop_heap. Comparing functor less and greater are employed for max heaps and min heaps correspondingly.

template<typename T> class DynamicArray

{

public:

void Insert(T num)

{

if(((minHeap.size() + maxHeap.size()) & 1) == 0)

{

if(maxHeap.size() > 0 && num < maxHeap[0])

{

maxHeap.push_back(num);

push_heap(maxHeap.begin(), maxHeap.end(), less<T>());

num = maxHeap[0];

pop_heap(maxHeap.begin(), maxHeap.end(), less<T>());

maxHeap.pop_back();

}

minHeap.push_back(num);

push_heap(minHeap.begin(), minHeap.end(), greater<T>());

}

else

{

if(minHeap.size() > 0 && minHeap[0] < num)

{

minHeap.push_back(num);

push_heap(minHeap.begin(), minHeap.end(), greater<T>());

num = minHeap[0];

pop_heap(minHeap.begin(), minHeap.end(), greater<T>());

minHeap.pop_back();

}

maxHeap.push_back(num);

push_heap(maxHeap.begin(), maxHeap.end(), less<T>());

}

}

int GetMedian()

{

int size = minHeap.size() + maxHeap.size();

if(size == 0)

throw exception("No numbers are available");

T median = 0;

if(size & 1 == 1)

median = minHeap[0];

else

median = (minHeap[0] + maxHeap[0]) / 2;

return median;

}

private:

vector<T> minHeap;

vector<T> maxHeap;

};

In the code above, function Insert is used to insert a new number deserialized from a stream, and GetMedian is used to get the median of the existing numbers dynamically.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

Email This BlogThis! Share to X Share to Facebook Share to Pinterest

Problem: Determine whether an input array is a post-order traversal sequence of a binary tree or not. If it is, return true; otherwise return false. Assume all numbers in an input array are unique.

For example, if the input array is {5, 7, 6, 9, 11, 10, 8}, true should be returned, since it is a post-order traversal sequence of the binary search tree in Figure 1. If the input array is {7, 4, 6, 5}, false should be returned since there are no binary search trees whose post-order traversal sequence is such an array.

Analysis: The last number is a post-order traversal sequence is the value of root node. Other numbers in a sequence can be partitioned into two parts: The left numbers, which are less than the value of root node, are value of nodes in left sub-tree; the following numbers, which are greater than the value of root node, are value of nodes in right sub-tree.

Take the input {5, 7, 6, 9, 11, 10, 8} as an example, the last number 8 in this sequence is value of root node. The first 3 numbers (5, 7 and 6), which are less than 8, are value of nodes in left sub-tree. The following 3 numbers (9, 11 and 10), which are greater than 8, are value of nodes in right sub-tree.

We can continue to construct the left sub-tree and right sub-tree according to the two sub-arrays with the same strategy. In the subsequence {5, 7, 6}, the last number 6 is the root value of the left sub-tree. The number 5 is the value of left child since it is less than root value 6, and 7 is the value of right child since it is greater than 6. Meanwhile, the last number 10 in subsequence {9, 11, 10} is the root value of right sub-tree. The number 9 is value of left child, and 11 is value of right child accordingly.

Let us analyze another array {7, 4, 6, 5}. The last number 5 is the value of root node. Since the first number 7 is greater than 5, there are no nodes in the left sub-tree and numbers 7, 4, 6 are all value of nodes in right sub-tree. However, we notice that a number 4, a value in right sub-tree, is less than the root value 5. It violates the definition of binary search trees. Therefore, there are no binary search trees with post-order traversal sequence {7, 4, 6, 5}.

It is not difficult to write code after we get the strategy above. Some sample code is shown below:

bool VerifySquenceOfBST(int sequence[], int length)

{

if(sequence == NULL || length <= 0)

return false;

int root = sequence[length - 1];

// nodes in left sub-tree are less than root node

int i = 0;

for(; i < length - 1; ++ i)

{

if(sequence[i] > root)

break;

}

// nodes in right sub-tree are greater than root node

int j = i;

for(; j < length - 1; ++ j)

{

if(sequence[j] < root)

return false;

}

// Is left sub-tree a binary search tree?

bool left = true;

if(i > 0)

left = VerifySquenceOfBST(sequence, i);

// Is right sub-tree a binary search tree?

bool right = true;

if(i < length - 1)

right = VerifySquenceOfBST(sequence + i, length - i - 1);

return (left && right);

Email This BlogThis! Share to X Share to Facebook Share to Pinterest

Question: Convert a binary search tree to a sorted double-linked list. We can only change the target of pointers, but cannot create any new nodes.

For example, if we input a binary search tree as shown on the left side of the Figure 1, the output double-linked list is shown on the right side.

Figure 1: The conversion between a binary search tree and a sorted double-linked list

A node of binary search tree is defined in C/C++ is as:

struct BinaryTreeNode

{

int m_nValue;

BinaryTreeNode* m_pLeft;

BinaryTreeNode* m_pRight;

};

Analysis: In a binary tree, each node has two pointers to its children. In a double-linked list, each node also has two pointers, one pointing to the previous node and the other pointing to the next one. Additionally, binary search tree is a sorted data structure. In a binary search tree, value in parent is always greater than value of its left child and less than value of its right child. Therefore, we can adjust a pointer to its left child in binary search tree to its previous node in a double-linked list, and adjust a pointer to its right child to its next node.

It is required that the converted list should be sorted, so we can adopt in-order traversal. That is because according to the definition of in-order traversal we traverse from nodes with less value to nodes with greater value. When we reach the root of the binary tree in Figure1, the tree may be viewed as three parts: a root with value 10, a left sub-tree with root value 6 and a right sub-tree with root value 14. According to the definition of sorted double-linked list, the root node with value 10 should be linked to the node with the greatest value (the node with value 8) in its left sub-tree, and it should be also linked to the node with the least value (the node with value 12) in its right sub-tree, as shown in Figure 2.

Figure 2: A tree with three parts: root, left sub-tree, right sub-tree. After we can the left sub-tree and right sub-tree, and we link them with the root, and then we can get a sorted double-linked list

According to the definition of in-order traversal, the sub-tree should be already converted to a sorted list when we reach its root (the node with value 10), and the last node in the sorted list should be the node with the greatest node (the node with value 8). If we link the last node in list to the root node of tree, then the root is the last node in list now. We continue to convert its right sub-tree, and connect the root to the node with its least value. How to convert its left sub-tree and right sub-tree? It should be similar to converting the whole tree. Therefore, we can solve it with recursion.

We can write the following code based on the recursive solution:

BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)

{

BinaryTreeNode *pLastNodeInList = NULL;

ConvertNode(pRootOfTree, &pLastNodeInList);

// pLastNodeInList points to the tail of double-linked list,

// but we need to return its head

BinaryTreeNode *pHeadOfList = pLastNodeInList;

while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)

pHeadOfList = pHeadOfList->m_pLeft;

return pHeadOfList;

}

void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)

{

if(pNode == NULL)

return;

BinaryTreeNode *pCurrent = pNode;

if (pCurrent->m_pLeft != NULL)

ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

pCurrent->m_pLeft = *pLastNodeInList;

if(*pLastNodeInList != NULL)

(*pLastNodeInList)->m_pRight = pCurrent;

*pLastNodeInList = pCurrent;

if (pCurrent->m_pRight != NULL)

ConvertNode(pCurrent->m_pRight, pLastNodeInList);

}

In the code above, pLastNodeInList is the last node (also the node with the greatest value) in the converted double-linked list. When we reach the value with 10, its left sub-tree has already been converted, and pLastNodeInList points to the node with 8. Afterwards we connect the root node to the linked list, and the node with 10 becomes the last node in the list (new node with the greatest value), so we move the pointer pLastNodeInList to the node with 10. We continue to invoke the function recursively with parameter pLastNodeInList to convert the right sub-tree. After we reach the left most node in the right sub-tree (also the node with least value), we linked it to the node with 10 in the list.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.

Email This BlogThis! Share to X Share to Facebook Share to Pinterest