Google Interview Question
Country: United States
Very nice solution. Simple implementation complexity: Time-O(N), Space O(logN)
Code:
class Node
{
public Node left = null; //Can also serve as previos and head in double linked list
public Node right = null; //Can also serve as next and tail in double linked list
public int data = 0;
public Node()
{
}
//Time: O(N), Space: O(log(N))
private Node Parse2LL(Node node)
{
if (node == null)
return null;
Node ret_list = new Node();
Node left_list = Parse2LL(node.left);
Node right_list = Parse2LL(node.right);
if (left_list != null) {
left_list.right.right = node;
ret_list.left = left_list.left;
}
else {
ret_list.left = node;
}
node.left = left_list;
if (right_list != null) {
right_list.left.left = node;
ret_list.right = right_list.right;
}
else {
ret_list.right = node;
}
node.right = right_list;
return ret_list;
}
//Time: 0(N), Space: 0(1)
public void FindCoeffs(Node node, int sum)
{
if (node == null) {
System.out.println("Not found");
return;
}
Node list = Parse2LL(node);
Node head = list.left;
Node tail = list.right;
while (head != tail)
{
if ((head.data + tail.data) < sum) {
tail = tail.left;
} else if ((head.data + tail.data) > sum) {
head = head.right;
} else {
System.out.println(String.format("Found {0}+{1}={2}.", head.data, tail.data, sum));
return;
}
}
}
You can traverse the tree, and for each node, find the necessary pair to sum to x.
public boolean existsSum(Node root, int x) { //In order traversal
boolean found = False;
Stack<Node> s = new Stack<Node>();
s.push(root);
while (!s.isEmpty()) { //n
Node y = s.peek();
if (y.left != null) {
s.push(y.left);
} else {
//Reached a leaf. Visit current node
s.pop();
int diff = x - y.value;
found = bstSearch(root, diff) > -1; //logn
if (y.right!=null) {
s.push(y.right);
}
}
}
}
public G bstSearch(Node<G> root, G x) {
int cmp = x.compareTo(root.value);
switch(cmp) {
case -1:
return bstSearch(root.left, x);
case 0:
return x;
case 1:
return bstSearch(root.right, x);
}
}
seems to me that bstSearch might have no end condition (if value is not present in the tree)
node bstSearch(node root, double x) {
if (node == null) return null;
if (node.value == x) return node;
if (node.value > x) return bstSearch(node.left, x);
if (node.value < x) return bstSearch(node.right, x);
}
bool findPair(node root, node treeStart, double x) {
if (node == null) return false;
if (bstSearch(treeRoot, treeRoot, x - root.value) != null)
return true;
return findPair(root.left, treeStart, x) || findPair(root.right, treeStart, x);
}
This can be done in O (N) time-complexity. But it will take O(log N) space complexity. Space for stack usage
Brief idea of algo:
1. Iterative inorder
2. two ways: one from increasing order and another decreasing order. For that we need two stacks. This is similar to processing sorted array and finding two elements whose sum is equal to given K.
1. Get left most element (smallest element) and get right most element (biggest element)
2. Also prepare both stacks: Increasing stack and decreasing stack
3. Get sum of both elements and it sum is equal to K then voilla we got answer otherwise check which direction we should move.
4. If new sum is less than K then we have to move increasing stack otherwise decreasing stack
5. Function nextIncreasingKey, nextDecreasingKey get next required value and also update required stack.
code is
static IntPair getPair (Tree root, int K) {
IntPair result = new IntPair ();
Stack incr = new Stack ();
Stack decr = new Stack ();
int leftkey = nextIncreasing (incr, root);
int rightkey = nextDecreasing (decr, root);
while (leftkey < rightkey) {
int sum = leftkey + rightkey;
if (sum == K) {
result.setFirst(leftkey);
result.setSecond(rightkey);
break;
}
else if (sum < K) {
leftkey = nextIncreasing (incr, root);
}
else {
rightkey = nextDecreasing (decr, root);
}
}
return result;
}
static private int nextDecreasing(Stack decr, Tree root) {
TreeNode node = (TreeNode) decr.pop();
if (node == null) {
node = updateDecreasingStack (decr, root.root);
}
else {
node = updateDecreasingStack (decr, node.left);
}
return node.key;
}
static private TreeNode updateDecreasingStack(Stack decr, TreeNode node) {
while (node != null) {
decr.push(node);
node = node.right;
}
return (TreeNode) decr.peek ();
}
static private int nextIncreasing(Stack incr, Tree root) {
TreeNode node = (TreeNode) incr.pop();
if (node == null) {
node = updateIncreasingStack (incr, root.root);
}
else {
node = updateIncreasingStack (incr, node.right);
}
return node.key;
}
static private TreeNode updateIncreasingStack(Stack incr, TreeNode node) {
while (node != null) {
incr.push(node);
node = node.left;
}
return (TreeNode) incr.peek ();
}
1. In-order traverse the tree.
2. As we visit each node, start a BST search starting from that node to the end node to find the second node that adds to the required sum.
3. You can stop traversing the tree when you reach a node whose value is greater than half of the required sum because the second node is always the greater than the first.
C++
#include <iostream>
#include <memory>
#include <vector>
class TreeNode;
using namespace std;
using TreeNodePtr = shared_ptr<TreeNode>;
class TreeNode {
public:
int value;
TreeNodePtr left;
TreeNodePtr right;
TreeNode(int v_):value(v_),left(nullptr),right(nullptr){}
};
TreeNodePtr findNode(TreeNodePtr n, int val) {
if(!n) return nullptr;
if(n->value == val) return n;
if(val < n->value) return findNode(n->left, val);
return findNode(n->right, val);
}
bool findSum(TreeNodePtr n, vector<TreeNodePtr> p, int sum) {
if(!n) return false;
int val = sum - p.back()->value;
auto end = p.end()-1;
while(true) {
TreeNodePtr other = nullptr;
if((*end)->value == val && *end != n) {
other = *end;
} else {
other = findNode((*end)->right, val);
}
if(other != nullptr) {
cout << n->value << " and " << other->value << endl;
}
if (end == p.begin()) {
break;
}
end--;
}
return false;
}
void traverse(TreeNodePtr t, vector<TreeNodePtr> &unvisited_parents, int sum) {
if(!t) return;
auto u = unvisited_parents;
u.push_back(t);
if(t->left) {
traverse(t->left, u, sum);
}
findSum(t, u, sum);
traverse(t->right, unvisited_parents, sum);
}
void addValueToBST(TreeNodePtr root, int val) {
if (val <= root->value) {
if(root->left) {
addValueToBST(root->left, val);
} else {
root->left = make_shared<TreeNode>(val);
}
} else {
if(root->right) {
addValueToBST(root->right, val);
} else {
root->right = make_shared<TreeNode>(val);
}
}
}
int main() {
auto root = make_shared<TreeNode>(10);
for (auto val : {3,4,9,1,7,3,-1,8,5,2,6,1,1}) {
addValueToBST(root, val);
}
vector<TreeNodePtr> unvisited_parents;
traverse(root, unvisited_parents, 7);
return 0;
}
We need to two stacks
1. For Iterative in order traversal ( which will traverse tree in increasing order)
2. For Iterative reverse in order traversal ( which will traverse tree in reverse order)
3. Now its simple just add two elements one from in order and other from reverse in-order if sum = required number this two are number
else if sum > required number then move reverse in-order for next number.
else move in- order traversal for next number.
You can use the same 2-sum algorithm over the tree. No need to serializing into an inorder or any other traversal.
Point 1: tree.Min();
Point 2: tree.Max();
The only operation needed is successor and predecessor (same as left and right in the array). To get the successor or predecessor you need O(1) operations.
Java Implementation.
Main idea from BST iterator and 2sum.
public class TwoSumInBST {
private TreeNode curtStart;
private TreeNode curtEnd;
private Stack<TreeNode> stackUp= new Stack<TreeNode>();
private Stack<TreeNode> stackDown = new Stack<TreeNode>();
public boolean getTwoSum(TreeNode root, int target) {
if (root == null) {
return false;
}
this.curtStart = root;
this.curtEnd = root;
TreeNode left = getFromUpToDown();
TreeNode right = getFromDownToUp();
while (left != right) {
int sum = left.value + right.value;
if (sum == target) {
return true;
}
if (sum < target) {
left = getFromUpToDown();
} else {
right = getFromDownToUp();
}
}
return false;
}
private TreeNode getFromUpToDown() {
while (curtStart != null) {
stackUp.push(curtStart);
curtStart = curtStart.left;
}
curtStart = stackUp.pop();
TreeNode res = curtStart;
curtStart = curtStart.right;
return res;
}
private TreeNode getFromDownToUp() {
while (curtEnd != null) {
stackDown.push(curtEnd);
curtEnd = curtEnd.right;
}
curtEnd = stackDown.pop();
TreeNode res = curtEnd;
curtEnd = curtEnd.left;
return res;
}
}
private TreeNode prev = null;
private TreeNode head = null;
void tree2ddl(TreeNode p){
if(p == null) return;
tree2ddl(p.left);
p.left = prev;
if(prev!=null) prev.right = p;
else head = p;
prev = p;
tree2ddl(p.right);
}
boolean id6386292369653760(TreeNode root, int target){
tree2ddl(root);
TreeNode tail = head;
while(tail.right!=null) tail=tail.right;
while(head!=tail){
int sum = head.val+tail.val;
if(sum == target) return true;
if(sum < target) head=head.right;
else tail=tail.left;
}
return false;
}
the problem can be easily solved when a sorted array but not a BST, actually a pre-order(Left-Root-Right) travel of a BST is a sorted array. similarly a anti pre-order(Right-Root-Left) travel of a BST is also a sorted array but by the opposite order.So, the answer is: suppose two node pointers p1 and p2, for p1 we do a pre-order travel on BST and for every node p1 point to, we do a anti pre-order travel on BST until p2->val + p1->val <= x, if equality is satisfied,the answer is YES, otherwise,we do one step on p1( move one pre-order step on BST ), and do p2 as we do in array.
1. Convert Binary tree itself to DoublyLink list
- Tester December 30, 2014[https] leetcode.com/2010/11/convert-binary-search-tree-bst-to.html
2. Since it is BST it is sorted then keep pointers one at start and one at tail.
3. Now its easy, add element at head and tail if sum is equal then print this two element.
if sum is less than sum asked then move head pointer else move tail pointer to left.
4. optional - convert back to BST from doubly- linklist
Complexity O(N)