No. 46 - Nodes with Sum in a Binary Search Tree

Problem: Given a binary search tree, please check whether there are two nodes in it whose sum equals a given value.


Figure 1: A sample binary search tree

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)

{
    stack<BinaryTreeNode*> nextNodes, prevNodes;
    buildNextNodes(pRoot, nextNodes);
    buildPrevNodes(pRoot, prevNodes);

    BinaryTreeNode* pNext = getNext(nextNodes);

    BinaryTreeNode* pPrev = getPrev(prevNodes);
    while(pNext != NULL && pPrev != NULL && pNext != pPrev)
    {
        int currentSum = pNext->m_nValue + pPrev->m_nValue;
        if(currentSum == sum)
            return true;

        if(currentSum < sum)

            pNext = getNext(nextNodes);
        else
            pPrev = getPrev(prevNodes);
    }

    return false;

}

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

{
    BinaryTreeNode* pNode = pRoot;
    while(pNode != NULL)
    {
        nodes.push(pNode);
        pNode = pNode->m_pLeft;
    }
}

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

{
    BinaryTreeNode* pNode = pRoot;
    while(pNode != NULL)
    {
        nodes.push(pNode);
        pNode = pNode->m_pRight;
    }
}

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

{
    BinaryTreeNode* pNext = NULL;
    if(!nodes.empty())
    {
        pNext = nodes.top();
        nodes.pop();

        BinaryTreeNode* pRight = pNext->m_pRight;

        while(pRight != NULL)
        {
            nodes.push(pRight);
            pRight = pRight->m_pLeft;
        }
    }

    return pNext;

}

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

{
    BinaryTreeNode* pPrev = NULL;
    if(!nodes.empty())
    {
        pPrev = nodes.top();
        nodes.pop();

        BinaryTreeNode* pLeft = pPrev->m_pLeft;

        while(pLeft != NULL)
        {
            nodes.push(pLeft);
            pLeft = pLeft->m_pRight;
        }
    }

    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.

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.

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.