underdog
BAN USER- 0of 0 votes
AnswersGiven a BST, with nodes having a parent pointer, 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.
- underdog in United States| Report Duplicate | Flag | PURGE
Amazon Software Development Manager Algorithm
Consider a tree formed by this input - 110, 75, 101, 100. You are given a pointer to node with value 100, and are searching for 75. Your first condition, if(value < node.data ) is satisfied at node(100), and then within that if condition your code would move to left subtree of 100, and so miss finding 75.
- underdog January 21, 2013You can. Is it better than 'walk up to the root and then a binary search for the value. Delete the common path between the path to root from node1 and from root to node2'.
It is not. If you do DFS, you are not even taking advantage of BST properties. A DFS will take O(E) time. E for BST is of the order N.
Walking up to the root, and doing a binary search would be O(log(N)) time. At worst you will be doing two walks; one up to the root, and one from root to the node2.
Can you put your algo here? Difficult to follow through the code without it. What is this random node business?
- underdog January 21, 2013