CareerCup

I have another solution:
Let given node be A, destination node be B
1) from A, traverse up following the pointer to parent until encounter three types of node, let the node be C
a. C is the root node
b. C with value bigger than the destination value
c. C node equals to the destination, then we got the path from A to B, return.
2) do the binary search on the right child tree of C to find B
3) If we find B, concatenate the path A -> C -> B, that's the answer.
The time complexity of this method is O(logN + logN) = O(logN)

//1) traverse from source node to the root node(top/first node) of BST.
At each traversal add the value of each node in a stack (say stack 1)
//2) traverse from the root node(top/first node) of BST to the destination node using InOrder .At each traversal add the value of each node in a stack (say stack 2)
//3) Compare stack1 with stack 2.
//3.1)if a node other than root node is common on both stack, then the path from source to destination will pass through that node skipping the root node. Print the values of stack 1 followed by stack 2.
//3.2)if there is no node other than root node is common on both stack, then the path from source to destination will pass through that root node. Print the values of stack 1 followed by stack 2.

//c#
public void path(Node _node)
{
if (_node == rootNode) { return; }
Stack1.push(_node.value);
path(Node _node.parentNode);
}

public void SearchRecord(Node _node, int _value)
{
if (_node == null) return 0;

if (_value < _node.value)
{
Stack2.push(_node.value);
SearchRecord(_node.leftNode, _value);
}
else if (_value > _node.value)
{
Stack2.push(_node.value);
SearchRecord(_node.rightNode, _value);
}
else if (_value == _node.value)
{
Stack2.push(_node.value);
return;
}
return;
}


public bool compare(Node _stack1Node,Node _stack2Node)
{
bool IsRepeated = false;
while(_stack1Node!= null)
{
while(_stack2Node != null_
{
if(_stack1Node.value == stack2Node.value)
{
IsRepeated = true;
}
}
_stack1Node=_stack1Node.nextNode;
}

return IsRepeated ;
}

Step 1: find node with given value.
Step 2: now keep on moving both pointer till reach root.
Problem reduced to two linked list having common node ( Like Y structure)

struct Node
{
int data;
struct Node *left;
struct Node *right;
struct Node *random;
struct Node *parent;
};
struct Node *NewNode(int data)
{
struct Node *temp=(struct Node *)malloc(sizeof(struct Node));
temp->data=data;
temp->left=NULL;
temp->right=NULL;
temp->parent=NULL;
temp->random=NULL;
return temp;
}

struct Node * Max(struct Node *first,struct Node *second,struct Node *third,int x)
{
if(!first && !second && !third)
return NULL;
if(!first && !second)
return third;
if(!first && !third)
return second;
if(!second && !third)
return first;
int a=first?first->data:-1;
int b=second?second->data:-1;
int c=third?third->data:-1;
struct Node *temp=NULL;
int val=0;
if(x==a)
return first;
else if(x==b)
return second;
else if(x==c)
return third;
if(a>b)
{
temp=first;
val=a;
}
else
{
temp=second;
val=b;
}
if(c>val)
{
temp=third;
val=c;
}
return temp;
}
struct Node * Min(struct Node *first,struct Node *second,struct Node *third,int x)
{
if(!first && !second && !third)
return NULL;
if(!first && !second)
return third;
if(!first && !third)
return second;
if(!second && !third)
return first;
int a=first?first->data:999;
int b=second?second->data:999;
int c=third?third->data:999;
struct Node *temp=NULL;
int val=0;
if(x==a)
return first;
else if(x==b)
return second;
else if(x==c)
return third;

if(a<b)
{
temp=first;
val=a;
}
else
{
temp=second;
val=b;
}
if(c<val)
{
temp=third;
val=c;
}
return temp;
}
bool Findpath(struct Node *node,int val)
{
if(!node)
return false;
if(node->data==val){
printf("%d",val);return true;}
if(node->data<val)
{
struct Node *temp=Max(node->right,node->random,node->parent,val);
if(Findpath(temp,val))
{
printf("%d",node->data);
return true;
}
}
else
{
struct Node *temp=Min(node->left,node->random,node->parent,val);
if(Findpath(temp,val))
{
printf("%d",node->data);
return true;
}
}
return false;
}

int main()
{
struct Node *node=NewNode(4);
node->left=NewNode(2);
node->left->left=NewNode(1);
node->left->right=NewNode(3);
node->right=NewNode(6);
node->right->left=NewNode(5);
node->right->right=NewNode(7);
node->right->right->right=NewNode(9);
node->right->right->right->left=NewNode(8);
node->left->parent=node;
node->right->parent=node;
node->left->left->parent=node->left;
node->left->right->parent=node->left;
node->right->left->parent=node->right;
node->right->right->parent=node->right;
node->right->right->right->parent=node->right->right;
node->right->right->right->left->parent=node->right->right->right;
node->random=node->left->right;
node->left->random=node->right;
node->left->left->random=node;
node->left->right->random=node->right->right;
node->right->random=node->right->right->right;
node->right->left->random=node->right->right->right->left;
node->right->right->random=node->right->right->right->left;
node->right->right->right->random=node->left->left;
node->right->right->right->left->random=node->left;
int val=8;
struct Node *find=node->left;
Findpath(find,val);
getchar();
return 0;
}

Each node in given tree (BST) has two pointers 1) parent node say p 2) random any other node say r.
So this forms another logical tree (with left and right pointers as p, r) where root is the current given node from which we want to find the path. Now we can traverse this new logical tree to find the target node with given value.
Obviously this assumes that newly formed structure with r and p pointers is forming a tree (ie, acyclic).

step1: compare the root and the given two value, move the root until two value are at different subtrees of the root ( now become root1)

step2: find the path of left node to the root1

step3: find the path of right node to the root1

Is there any use of the pointer that points to any node?

1) if value == node.data then break
2) if(value < node.data )
a. if node is a right child of its parent and value is less than parent.data , move to parent
else
move to left subtree of the node

3) if(value > node.data)
a. if node is a left child of its parent and value is greater than parent.data, move to parent
else
move to right subtree of the data

4) continue until node is null or node.data == value

this would find a path whether the value exits in the subtrees of the node or anywhere else.

void findPath(Node node, int value) {
          
     if(node == null )
           throw new RtE();
             
     while(node != null) {
           
            System.out.println(node.data);
            if (node.data == value)
                     return;
          
             boolean isLeftChild = false, isRightChild = false;
          
             Node parent = node.parent;
             if(parent != null) {
                
                 if( parent.left == node)  
                           isLeftChild = true; 
                 else 
                          isRightChild  = true;  
              }
              if( value < node.data) {
                
                  if(isRightChild && value < parent.data)
                             node = parent;
                  else
                          node = node.left; 
               } else {
                   if(isLeftChild && value > parent.data )
                           node = parent;
                  else
                           node = node.right;
              }                         
    }

}

Probably full of errors, but why wouldn't something like this work. Just traverse from the current node until you find the value or reach a null child.

ArrayList<Node> findPath(Node start, int toFind){
	ArrayList<Node> path = new ArrayList<Node>();
	Node curr = start;
	while(curr != null && curr.value != toFind){
		path.add(curr);
		if(curr.value > toFind && curr.parent().value > toFind){
			curr = curr.parent();
		} else if(curr.value < toFind && curr.parent() < toFind){
			curr = curr.parent();
		} else if(curr.value > toFind){
			curr = curr.left();
		} else{
			curr = curr.right();
		}
	}
	if(path.get(path.size()-1).value == toFind){
		return path;
	}
	return null;

Start by adding the pointer to a stack. Add pointers of parents to the stack until you reach to root. You can then start at the root and search for the data value of the second node. If the top of the stack is the same as a node in the path, you pop. once you stop popping, you have found the most common ancestor (you must keep track of the last popped node to put it back on the stack). If you do not find a common ancestor but have found the initial node, your value is a descendant of it and you can continue adding pointers to your stack resulting in a stack with your path. O(logN).

First start moving from given node to till root. Once we get the root, this problem become like to get LCA. and the path we travel for that would be the "path from the given node (pointer), to the node with the given value".

Move the given node until we get root node or destination node. keep all the traversal node into the stack. if we get destination node break the loop and return all stack values else we reach to root then check both are not less than and not greater than from root. it means both are in different side.
if destination is greater than go right else go left and check the same condition. if both are same side then pop the value and move to that time until we get destination. In this case stack have all the node which we have to travel while going from given node to destination.

public ArrayList<Node> findPath(Node in, int val) {
ArrayList<Node> path = new ArrayList<Node>();

Node current = in;
while (current != null){
path.add(current);
if(val == current.getData()){
return path;
} else if (val < current.getData()) {
current = current.getLeftChild();
} else if (val > current.getData()) {
current = current.getRightChild();
}
}

if (current.getData() < val) {
ArrayList<Node> upperPath = new ArrayList<Node>();
current = in;

while(current != null){
upperPath.add(current);
if(val == current.getData()){
return path;
} else if (current == current.getParent().getRightChild()){
current = current.getParent();
} else {
current = current.getParent();
Node savedCurrent = current;

current = current.getRightChild();
ArrayList<Node> shortPath = new ArrayList<Node>();
while (current != null){
shortPath.add(current);
if(val == current.getData()){
upperPath.add(savedCurrent);
upperPath.addAll(shortPath);
return upperPath;
} else if (val < current.getData()) {
current = current.getLeftChild();
} else if (val > current.getData()) {
current = current.getRightChild();
}
}
current = savedCurrent;
}
}
} else {
ArrayList<Node> upperPath = new ArrayList<Node>();
current = in;

while(current != null){
upperPath.add(current);
if(val == current.getData()){
return path;
} else if (current == current.getParent().getLeftChild()){
current = current.getParent();
} else {
current = current.getParent();
Node savedCurrent = current;

current = current.getLeftChild();
ArrayList<Node> shortPath = new ArrayList<Node>();
while (current != null){
shortPath.add(current);
if(val == current.getData()){
upperPath.add(savedCurrent);
upperPath.addAll(shortPath);
return upperPath;
} else if (val < current.getData()) {
current = current.getLeftChild();
} else if (val > current.getData()) {
current = current.getRightChild();
}
}
current = savedCurrent;
}
}
}
return null;

}

public ArrayList<Node> findPath(Node in, int val) {
        ArrayList<Node> path = new ArrayList<Node>();
        
        Node current = in;
        while (current != null){
            path.add(current);
            if(val == current.getData()){
                return path;
            } else if (val < current.getData()) {
                current = current.getLeftChild();
            } else if (val > current.getData()) {
                current = current.getRightChild();
            }
        }
        
        if (current.getData() < val) {
            ArrayList<Node> upperPath = new ArrayList<Node>();
            current = in;

            while(current != null){
                upperPath.add(current);
                if(val == current.getData()){
                    return path;
                } else if (current == current.getParent().getRightChild()){
                    current = current.getParent();    
                } else {
                    current = current.getParent();
                    Node savedCurrent = current;

                    current = current.getRightChild();
                    ArrayList<Node> shortPath = new ArrayList<Node>();
                    while (current != null){
                        shortPath.add(current);
                        if(val == current.getData()){
                            upperPath.add(savedCurrent);
                            upperPath.addAll(shortPath);
                            return upperPath;
                        } else if (val < current.getData()) {
                            current = current.getLeftChild();
                        } else if (val > current.getData()) {
                            current = current.getRightChild();
                        }
                    }
                    current = savedCurrent;
                }
            }    
        } else {
            ArrayList<Node> upperPath = new ArrayList<Node>();
            current = in;

            while(current != null){
                upperPath.add(current);
                if(val == current.getData()){
                    return path;
                } else if (current == current.getParent().getLeftChild()){
                    current = current.getParent();    
                } else {
                    current = current.getParent();
                    Node savedCurrent = current;

                    current = current.getLeftChild();
                    ArrayList<Node> shortPath = new ArrayList<Node>();
                    while (current != null){
                        shortPath.add(current);
                        if(val == current.getData()){
                            upperPath.add(savedCurrent);
                            upperPath.addAll(shortPath);
                            return upperPath;
                        } else if (val < current.getData()) {
                            current = current.getLeftChild();
                        } else if (val > current.getData()) {
                            current = current.getRightChild();
                        }
                    }
                    current = savedCurrent;
                }
            }    
        }
        return null;
        
    }

I find that we can improve the algorithm still with no additional space required and lesser no of node accesses.

- traverse from the "given node" towards the root
- at every node (cur_node) on the path, check for the following :

if (current value matches the given value) then path is found
else (if the to_find value is in between current value and parent value then to_find value is either in other subtree of the parent or directly under the "given node")

once we know the subtree in which to_find value is present, we can traverse the path conduction a binary search

for to_find value to be in between current value and parent value either of the following 2 conditions must be true

- current value > parent value and to_find value > parent value and to_find value < current value
- current value < parent value and to_find value < parent value and to_find value > current value

This algo should work in O(logN) time without any extra space

Do let me know if you see any flaws/deviating cases in the logic

The question was confusingly stated. It should have been
There's a BST, with each node having a parent pointer. Given that BST, a pointer to a node (any node), and a value, find the path from the given node (pointer) to the node with the given value.


Assuming the tree is balanced, you can do it in O(log n) time.
Find the lowest common ancestor for the two nodes using the parent pointers. Then it's just a matter of unioning the path from the two nodes to the lowest common ancestor.
Or even better.
If P1 is the path from A to the root and P2 is the path from B to the root. Path from A to B is (P1 - P2) U (P2 - P1), where the subtraction operation is performed on the edges.

Can't we do a DFS and and get the path....

//1) traverse to the root node(top/first node) of BST and calculate the length.
//c#
public int path(Node _node)
{
if (_node == rootNode) { return 0; }
return 1 + path(Node _node.parentNode);
}

//2) traverse from the root node(top/first node) of BST to the destination node using InOrder and calculate the length.
//c#
public int InOrder(Node _node,Node _destinationNode)
{
if (_node == _destinationNode) return 0;
return 1 + InOrder(_node.leftNode, _destinationNode);
return 1 + InOrder(_node.rightNode, _destinationNode);
}

what time complexity for evulating a postfix expression ?