Geek asks and answers

Find two numbers from BST whose sum corresponds to a given number K

Given a BST with unique integers and K. Find the pair (a, b) in BST so that a + b = k.

Limitations:

You cannot change the structure of the tree, otherwise we could convert it to a sorted doubly linked list and foiund the pair to O (N).

The approach should be in place.

O (N).

I thought about how to start two pointers, one from left to right, and the other from right to left in the same way as when searching for a pair in a sorted array. But I could not understand how to implement it?

+5
source share
5 answers

, , . , ( ) ( ). (a + b) > k, ( ), ( ). , a >= b . node .

, . , . - :

a = b = root;
while (a.left) {
    astack.push(a)
    a = a.left
}
while (b.right) {
    bstack.push(b)
    b = b.right
}


while (a.value < b.value) {
    if (a.value + b.value == k) found!
    if (a.value + b.value < k) {
        if (a.right){
            a = a.right
            while (a.left) {
                astack.push(a)
                a = a.left
            }
        } else a = astack.pop()
    } else {
        if (b.left){
            b = b.left
            while (b.right) {
                bstack.push(b)
                b = b.right
            }
        } else b = bstack.pop()
    }
}
+7

, . . , , /, . , , . , , , .

. HashSet. , target_sum . .

- O (n) , O (n) , .

+2

BST Normal Inorder and Reverse Inorder. node, node. node, node. . , true. , node , node . - , false.

   boolean isPairPresent(Node3 root, int sum) 
   {
    Stack<Node3> stack1 = new Stack<Node3>();
    Stack<Node3> stack2 = new Stack<Node3>();

    boolean done1 = false;
    boolean done2 = false;

    int val1 = 0, val2 = 0;
    Node3  curr1 = root, curr2 = root;

    while(true) {

        while(done1 == false)   {
            if(curr1 != null)   {
                stack1.push(curr1);
                curr1 = curr1.left;
            } else {
                if(stack1.isEmpty())
                    done1 = true;
                else    {
                    curr1 = stack1.pop();
                    val1 = curr1.data;
                    curr1 = curr1.right;
                    done1 = true;
                }
            }   
        }

        while(done2 == false)   {
            if(curr2 != null)   {
                stack2.push(curr2);
                curr2 = curr2.right;
            } else {
                if(stack2.isEmpty())
                    done2 = true;
                else {
                    curr2 = stack2.pop();
                    val2 = curr2.data;
                    curr2 = curr2.left;
                    done2 = true;
                }
            }
        }

        if((val1 != val2) && (val1+val2 == sum))    {
            System.out.println("Pair found: "+val1+" + "+val2+" = "+sum);
            return true;
        } else if(val1 + val2 > sum) {
            done2 = false;
        } else if(val1 + val2 < sum)
            done1 = false;

        if(val1 >= val2)
            return false;
    }
}
+1

Another solution to the above problem (O (n) space is required, but the implementation is much simpler than searching for the next larger / smaller element in BST) Crawl through the given binary tree and store the elements in an array. The resulting array will be sorted. Start by comparing A [1] + A [n] with k

Initialize i=1, j=n

while(A[i]+A[j] <> k)
if A[i]+A[j] < k
  i++;
else
  j--;// typo
0
source

First traverse the tree in order and save the result to Array a[], and then

i = 0 ; j = n;
while(i<=j<=n)
{
  if(a[i]+a[j] == k)
  {
    printf("pair is == %d & %d \n", a[i],a[j]);
    i++;
  }
  else if(a[i]+a[j] > k)
    j--;
  else if(a[i]+a[j] < k)
    i++;
}
0
source

More articles:


All Articles