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.

No. 45 - Closest Node in a Binary Search Tree

Problem: Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k.

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

Figure 1: A sample binary search tree, in which the closest node to 29 is the node with value 28

Analysis: Let’s analyze this problem step by step, taking the binary search in Figure 1 and 29 as an example.

We start from the root node with value 32, and the distance to 29 is 3. Since the value 32 is greater than 29, and all values in the right sub-tree are greater than 32, distances to 29 in the right sub-tree should be greater than 3. We move to the left sub-tree.

The next node to be visited contains value 24, and the distance to 29 is 5. Since 5 is greater than the previous closest distance 3, the closest node up to now remains the node with value 32. Additionally, the current value 24 is less than 29, and all values in the left sub-tree are less than 24, so distances to 29 in the left sub-tree will be greater than 5. We move on to visit the right sub-tree.

The next node to be visited contains value 28, and the distance to 29 is 1. Since 1 is less than the previous closest distance 3, the closest node is updated to the node with value 28. Additionally, the value 28 is less than 29, and all values in the left sub-tree areless than 28, so distances to 29 in the left sub-tree will be greater than 1. Let’s continue to visit the right sub-tree.

Finally we reach a left node with value 31. The distance to 29 is 2 and it is greater than the previous closest distance 1, so the closest node to 29 is still the node with value 28.

According to the step-by-step analysis above, we could implement the following code:

BinaryTreeNode* getClosestNode(BinaryTreeNode* pRoot, int value)
{
    BinaryTreeNode* pClosest = NULL;
    int minDistance = 0x7FFFFFFF;
    BinaryTreeNode* pNode = pRoot;
    while(pNode != NULL)
    {
        int distance = abs(pNode->m_nValue - value);
        if(distance < minDistance)
        {
            minDistance = distance;
            pClosest = pNode;
        }

        if(distance == 0)

            break;

        if(pNode->m_nValue > value)

            pNode = pNode->m_pLeft;
        else if(pNode->m_nValue < value)
            pNode = pNode->m_pRight;
    }

    return pClosest;

}
 

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.

No. 40 - Add on Lists

Problem: Nodes in a list represent a number. For example, the nodes in Figure 1 (a) and (b) represent numbers 123 and 4567 respectively. Please implement a function/method to add numbers in two lists, and store the sum into a new list.

Figure 1: Two lists representing numbers. (a) A list for 123; (b) A list for 4567.

Analysis: Usually numbers are added beginning from the least significant digits (The digit 3 in the number 123, and the digit 7 in the number 4567). As shown in Figure 1, the least significant digits are at the tail of lists, and they can be accessed after the whole lists are scanned. Therefore, lists should be reversed at first, in order get the least significant digits before other digits. The two reversed lists of lists in Figure 1 are shown in Figure 2.

Figure 2: Two reversed lists of the lists in Figure 1.

After two lists are reversed, we can add nodes along the links between nodes, and then reversed the result list after all nodes are added. Therefore, the overall structure to add numbers in two lists can be implemented with the following code in C/C++:

ListNode* Add(ListNode* pHead1, ListNode* pHead2)

{

    if(pHead1 == NULL || pHead2 == NULL)

        return NULL;

    pHead1 = Reverse(pHead1);

    pHead2 = Reverse(pHead2);

    ListNode* pResult = AddReversed(pHead1, pHead2);

    return Reverse(pResult);

}

Now let’s implement the function AddReversed, to add nodes in two reversed lists. Digits are gotten in nodes along links between nodes. When we get two digits in two lists, we add them and create a new node to store the sum, and append the new node into the list for result. There are two issues worthy of attention: (1) The length of two lists might be different; (2) The sum of two digits may be greater than 10, so we have to take care of the carry when adding two digits. The function AddReversed can be implemented with the following C/C++ code:

ListNode* AddReversed(ListNode* pHead1, ListNode* pHead2)

{

    int carry = 0;

    ListNode* pPrev = NULL;

    ListNode* pHead = NULL;

    while(pHead1 != NULL || pHead2 != NULL)

    {

        ListNode* pNode = AddNode(pHead1, pHead2, &carry);

        AppendNode(&pHead, &pPrev, pNode);

        if(pHead1 != NULL)

            pHead1 = pHead1->m_pNext;

        if(pHead2 != NULL)

            pHead2 = pHead2->m_pNext;

    }

    if(carry > 0)

    {

        ListNode* pNode = CreateListNode(carry);

        AppendNode(&pHead, &pPrev, pNode);

    }

    return pHead;

}

The function AddNode adds digits in two nodes. The third parameter of this function takes the carry for addition calculation, as listed below:

ListNode* AddNode(ListNode* pNode1, ListNode* pNode2, int* carry)

{

    int num1 = 0;

    if(pNode1 != NULL)

        num1 = pNode1->m_nValue;

    int num2 = 0;

    if(pNode2 != NULL)

        num2 = pNode2->m_nValue;

    int sum = num1 + num2 + *carry;

    *carry = (sum >= 10) ? 1 : 0;

    int value = (sum >= 10) ? (sum - 10) : sum;

    return CreateListNode(value);

}

The function AppendNode is used append a node into the tail of lists. In order to avoid scanning the whole list to get the previous tail every time, the previous tails is stored in the parameter/variable pPrev, as listed in the following code:

void AppendNode(ListNode** pHead, ListNode** pPrev, ListNode* pNode)

{

    if(*pHead == NULL)

        *pHead = pNode;

    if(*pPrev == NULL)

        *pPrev = pNode;

    else

    {

        (*pPrev)->m_pNext = pNode;

        *pPrev = pNode;

    }

}

The function CreateListNode is to create a list node according to a value, which is omitted here because it’s quite straightforward. 

The steps to reverse a list are discussed in my previous blog.

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. 

No. 39 - Stacks Sharing an Array

Problem 1: How can you implement two stacks in a single array, where no stack overflows until no space left in the entire array space?

Analysis: An array has two ends, so each of the two stacks may grow from an end in the array. Figure 1 below shows the initial status of the array and two stacks (assuming the capacity of the array is 10).

Figure 1: Initial status of the array and two stacks

Since two stacks are empty at first, so indexes of top items are initialized as -1 and 10 at first.
When items are pushed into first stack, it grows from left to right. Similarly, the second stack grows from right to left when items are items are pushed into it. For example, Figure 2 shows the status when three items a, b and c are pushed into the first stack, and d, e are pushed into the second stack.

Figure 2: The status after three items are pushed into the first stack and two items are pushed into the second stack 

No more items can be pushed into stacks when two top items are adjacent to each other, because all space in the array has been occupied.

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

template <typename T, int capacity> class TwoStacks

{

public:

    TwoStacks()

    {

        topFirst = -1;

        topSecond = capacity;

    }

    T top(int stackIndex)

    {

        validateIndex(stackIndex);

        if(empty(stackIndex))

            throw new exception("The stack is empty.");

        if(stackIndex == 0)

            return items[topFirst];

        return items[topSecond];

    }

    void push(int stackIndex, T item)

    {

        validateIndex(stackIndex);

        if(full())

            throw new exception("All space has been occupied.");

        if(stackIndex == 0)

            items[++topFirst] = item;

        else

            items[--topSecond] = item;

    }

    void pop(int stackIndex)

    {

        validateIndex(stackIndex);

        if(empty(stackIndex))

            throw new exception("The stack is empty.");

        if(stackIndex == 0)

            --topFirst;

        else

            ++topSecond;

    }

    bool empty(int stackIndex)

    {

        if(stackIndex == 0 && topFirst == -1)

            return true;

        if(stackIndex == 1 && topSecond == capacity)

            return true;

        return false;

    }

private:

    bool full()

    {

        return (topFirst >= topSecond - 1);

    }

    void validateIndex(int stackIndex)

    {

        if(stackIndex < 0 || stackIndex > 1)

            throw new exception("Invalid Stack Index.");

    }

private:

    T items[capacity];

    int topFirst;

    int topSecond;

};

Problem 2: How can you implement n (n > 2) stacks in a single array, where no stack overflows until no space left in the entire array space?

Analysis: An array only has two ends, so we need new strategies to implement more than two stacks in a single array.

We may implement the array like a list, where each item in the array has a link to another item. When an item has not been occupied by any stacks and it is available, it is linked to the next available item. When an item is pushed into a stack, it is linked to the previous item in the stack. That’s to say, there are n + 1 list in total in the system if there are n stacks sharing an array, a list for the available space left in the array, and a list for each stack.

Let’s take three stacks sharing an array with capacity 10 as an example. Figure 3 shows the initial status for the array and stacks. Each item in the array has two blocks, one for item data and the other for the index of another block.

Figure 3: Initial status of three stacks sharing an array

As shown in Figure 3, each item is linked to the next item (the link block of the i^th item is i+1). The head of list for available items in the array points to the item at position 0, which is the Ava pointer in the figure. Since three stacks are empty, their top (Top1, Top2 and Top3 in the figure) are initialized as -1.

Let’s try to push an item a into the first stack. Currently the first available item is at the position 0, so we set its data block as a. The link block of the item is 1, which means the next available item is at the position 1, so we update the Ava pointer to the position 1. Additionally, the link block of the item at the position 1 should be updated to -1, the previous top index of the first stack. Lastly, we update to top index of the first stack to 0. The status of the array and stacks are shown in Figure 4.

Figure 4: The status after pushing a into the first stack

Let’s push two more items b and c into the first stack. The operations are similar as before, and the status is shown in Figure 5.

Figure 5: The status after adding two more items, b and c, into the first stack

In the next step we are going to push another d into the second stack. Most operations are similar as before. The link block in the item at the position 3 is updated to -1, since the second stack is empty before and its top index is -1 previously. And then the top index of the second stack is updated to 3. The status after adding d into the second stack is shown in Figure 6.

Figure 6: The status after pushing d into the second stack

If we continue to push three more item e, f, and g into the second stack, the status is shown in Figure 7.

Figure 7: The status after pushing three more items, e, f, and g, into the second stack

At this time we are going to pop an item from the first stack. Since the top index of the first stack is 2, the item to be popped off is at the position 2. The link value in that item is 1, which means the previous top in the first stack is at the position 1 in the array, so we update the top index of the first stack as 1. Now the item at the position 2 becomes available, it should be linked to the list for available items. We move the Ava pointer to 2, and then update the link value of the item at the position 2 as 7, which is the previous head position of the list for available items. The status is shown in Figure 8.

Figure 8: The status after popping an item from the first stack

If we pop an item off the second stack, the item at the position 6 will be linked to the list for available items too. Figure 9 depicts the status after the related operations.

Figure 9: The status after popping an item off the second stack

If we push h into the third stack, it will be placed into the item at the position 6 because Ava points to that item. The next available item is at the position 2 (the link value in the item at the position 6). Therefore, the head of the list for available items points to location 2, as shown in Figure 10.

Figure 10: The status after pushing h into the third stack

Let’s continue to push four more items into the third stack, i, j, k, and l. The status after these four items are pushed is shown in Figure 11. At this time, there are two items in the first stack (a and b), three items in the second stack (d, e and f), and five items in the third stack (h, i, j, k, and l). Please note that items inside a stack are not necessarily adjacent. 

Figure 11: The status after pushing i, j, k, l into the third stack

After l is pushed into the item at the position 9, the Ava pointer is update to -1 (the previous link value in the item at the position 9), which means all items in the array have been occupied by stacks. We can’t push more items until some items are popped off.

The source code in C++ to implement stacks sharing an array is listed below:

template <typename T, int capacity, int count> class Stacks

{

public:

    Stacks()

    {

        int i;

        for(i = 0; i < capacity - 1; ++i)

            items[i].link = i + 1;

        items[i].link = -1;

        emptyHead = 0;

        for(i = 0; i < count; ++i)

            stackHead[i] = -1;

    }

    T top(int stackIndex)

    {

        validateIndex(stackIndex);

        if(empty(stackIndex))

            throw new exception("The stack is empty.");

        return items[stackHead[stackIndex]].data;

    }

    void push(int stackIndex, const T& item)

    {

        validateIndex(stackIndex);

        if(full())

            throw new exception("All space has been occupied.");

        Item<T>& block = items[emptyHead];

        int nextEmpty = block.link;

        block.data = item;

        block.link = stackHead[stackIndex];

        stackHead[stackIndex] = emptyHead;

        emptyHead = nextEmpty;

    }

    void pop(int stackIndex)

    {

        validateIndex(stackIndex);

        if(empty(stackIndex))

            throw new exception("The stack is empty.");

        Item<T>& block = items[stackHead[stackIndex]];

        int nextItem = block.link;

        block.link = emptyHead;
        emptyHead = stackHead[stackIndex];

        stackHead[stackIndex] = nextItem;

    }

    bool empty(int stackIndex)

    {

        return (stackHead[stackIndex] < 0);

    }

private:

    void validateIndex(int stackIndex)

    {

        if(stackIndex < 0 || stackIndex >= count)

            throw new exception("Invalid index of stack.");

    }

    bool full()

    {

        return (emptyHead < 0);

    }

private:

    template <typename T> struct Item

    {

        T data;

        int link;

    };

private:

    Item<T> items[capacity];

    int emptyHead;

    int stackHead[count];

};

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.