CareerCup

Find the LCA of x and z(takes O(n)+O(n) time). There are 2 possibilites:
1. LCA is either x or z, in the case traverse the nodes from LCA to non-LCA node and if y occurs in the path return TRUE.(O(n) time)
2. LCA is neither x nor z. In this case, traverse the nodes between LCA and x and LCA and y, if you found y in any of them, return TRUE. (O(n)+O(n)) time

Overall time complexity=O(n)
Space complexity=O(1)

If parent pointer is not available we have to first traverse the tree and set parent pointers.
First check if x,y,z lies in tree.
Run a DFS from x to z and search for y.

please explain what is meant by path.

First find Y. Now if you remove node Y from the tree, you have at most 3 trees.
1st tree with Y->left as root
2nd tree with Y->right as root
3rd tree is rest of the original tree
Now check if X and Z lies in different trees. if yes, then Y lies between X and Z

a
/ \ x z a
y b -> after removal of y -> / \ \
/ \ \ d e b
x z c \
/ \ c
d e

Of course before returning true, you have to re-attach the tree.

bool _test(node *root, int x, int y, int z, int *count);

bool test(node *root, int x, int y, int z)
{
   int count = 0;
   return _test(root,x,y,z,&count);
}

bool _test(node *root, int x, int y, int z, int *count)
{
   if(root == NULL)
   {
	  return false;
   }
   if(root->data == x)
   {
     (*count)++;
   }
   if((*count) == 1 && root->data == y)
   {
	 (*count)++;
   }
   if((*count) == 2 && root->data == z)
   {
	  return true;
   }

   bool left =  _test(root->left,x,y,z,count);
   bool right = _test(root->right,x,y,z,count);

   if(left == true || right == true)
   {
		return true;
   }

   if((*count) == 1 && root->data == x)
   {
     (*count)--;
   }
   if((*count) == 2 && root->data == y)
   {
	 (*count)--;
   }
}

This can be a simplest solution with complexity n(log n)
call find_path function for every 'y' node.

int find_path(node * ptr)
{
bool x_left = false, z_left = false;
bool x_right = false, z_right = false;
// search for x & z on left side
if(ptr->left)
find_xz(ptr->left, &x_left, &z_left);

// search for x & z on right side
if(ptr->right)
find_xz(ptr->left, &x_right, &z_right);

// if x found on left side and z on right then return true
// if x found on right side and z found on left side then return true
if((x_left && z_right)
||(x_right && z_left))
return true;

return false;
}

find_xz(node * ptr, int * x, int * z)
{
// if x or z found then mark corrosponding input parameter as true.
if(ptr->value == 'x')
*x = true;
if(ptr->value == 'z')
*z = true;

// if both x & z found then return
if(*x == true && *z == true)
return;

// search for x & z left side
if(ptr->left)
find_xz(ptr->left, x, z);

// search for x & z right side
if(ptr->right)
find_xz(ptr->right, x, z)
return;
}

String x, y, z; // globals
bool yconnect (node* head){
String path = "";
void helper(head, path);
int xlength,ylength,zlength;
xlength = x.length();
ylength = y.length();
zlength = z.length();
if(xlength < ylength && < zlength){
if(x == y.substr(0, xlength) && x == z.substr(0, xlength)){
return true;
}
else{
return false;
}
}
else if(ylength < zlength){
if(y = x.substr(0, ylength) && x = z.substr(0,xlength)){
return true;
}
else{
return false;
}
}
else{ //zlength < ylength
if(z = x.substr(0, zlength) && x = y.substr(0,xlength)){
return true;
}
else{
return false;
}
}
}

void helper(node * head, String path){
if(head->data == 'x'){
x = path;
}
else if(head->data == 'y'){
y = path;
}
else if(head->data == 'z'){
z = path;
}
if (head->left != null){
helper(head->left, path.append("L"));
}
if (head->right != null){
helper(head->right, path.append("L"))
}
}

as it is a binary tree not binary search tree,
we have to do more work minimum time complexity will be O(n)
simply do inorder traversal of this tree,note the position of y wrt to x and z,it must be central if it is not then say false,else if it is central than one more test has to be performed to confirm , then perform post order traversal note the position of y with respect to x and z it must be after the x and z.

1) Find common ancestor, say w, of x and z.
2) Find whether y comes in path of w to x OR w to z.

I guess just a preorder should do.. if y comes before atleast one of the other 2 nodes, then it means there is a path between x & z through y.

create a path and also check for Y, by doing breath first search with starting node as X & end node as Z, if y exist then return true. since BT is also a graph!

Use depth-first search because it's not a BST. BT simplifies the problem, since each node is part of a sub-linked list:

Two possibilities:
X->...->Y...->...Z or Z->...-> Y -> ... -> X
1. Find X or Z first and mark as visited. If Y found first, return false.
2. Find Y and mark as visited; if X/Z found instead, return false.
3. Find X/Z as end of path, and mark as visited. If found, return true.

How about this solution ...

There is three case :-
1. x-> y-> z
2. z - > y ->x
3rd case in which (x or z)lies in left subtree and (z or x) lies in right subtree.

int ispath(node *root,node *x,node *y,node *z){
if(root==Null)
return 0;
if(root==y){
yflag=1;
if(xflag==1 || zflag==1)
return ispath(root->left,x,y,z) || ispath(root->right,x,y,z);
else
return ispath(root->left,x,y,z) && ispath(root->right,x,y,z);
}
elseif(root==x){
xflag=1;
if(yflag==1)
return 1;
elseif(zflag==1)
return 0;
else
return ispath(root->left,x,y,z) || ispath(root->right,x,y,z);
}
elseif(root==z){
zflag=1;
if(yflag==1)
return 1;
elseif(xflag==1)
return 0;
else
return ispath(root->left,x,y,z) || ispath(root->right,x,y,z);
}.

else
return ispath(root->left,x,y,z) || ispath(root->right,x,y,z);
}


Note:- xflag ,yflag and zflag global variables.

I have been thinking about this problem in-depth specifically to cover all the boundary cases and came up with the following. Please let me know if anyone can find an uncovered case.
The algo is:
1. If either x is in subtree(y) OR z is in subtree(y) then return TRUE.
2. If both x is in subtree(y) AND z is in subtree(y) then If LCA(x, z) == y then return TRUE
3. Else all other conditions, return FALSE

The code is:
private static boolean liesInPath(TreeNode root, TreeNode x, TreeNode y, TreeNode z) {
int countMatches = countMatchesPQ(y, x, z);
if(countMatches == 1) {
return true;
}
if(countMatches == 2) {
if(leastCommonAncestor(root, x, z) == y) {
return true;
}
}
return false;
}

private static int countMatchesPQ(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return 0;
}
int matches = countMatchesPQ(root.left, p, q) + countMatchesPQ(root.right, p, q);
if(root == p || root == q) {
return matches + 1;
}
else {
return matches;
}
}

private static TreeNode leastCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || p == null || q == null) {
return null;
}
if(root == p || root == q) {
return root;
}
int totalMatches = countMatchesPQ(root.left, p, q);
if(totalMatches == 1) {
return root;
}
else if(totalMatches == 2) {
return leastCommonAncestor(root.left, p, q);
}
else {
return leastCommonAncestor(root.right, p, q);
}
}

Flawless code ... Enjoy!!

// returns true if root has 'n'
bool has(node* root, node* n)
{
	if(!root)
		return false;
	else if(root == n)
		return true;
	else
		return has(root->left, n) || has(root->right, n);
}

// check if Y lies on path between X and Z
bool isYonXZ(node* root, node* x, node* y, node* z)
{
	if(!root || !x || !y || !z || !has(root,x) || !has(root,y) || !has(root,z))
                return false;
	else if(has(y->left,x) && has(y->left,z))
		return false;
	else if(has(y->right,x) && has(y->right,z))
		return false;
	else if(!has(y,x) && !has(y,z))
		return false;
	else
		return true;
}

If each distinct route starting from the root to leaf node is considered as a path, we need to determine if there is a route from root to leaf which contains nodes x, y, z such that pathindex(y) > pathindex(x) and pathndex(y) < pathindex(z). The below code considers each path and determines if x,y,z exists satisfying the condition on their positions.

First defining the TreeNode class:
******

package trees;

public class TreeNode {

	private int data;
	private TreeNode left;
	private TreeNode right;
	private Boolean isVisited = false;
	
	public TreeNode(int d){
		this.data = d;
	}
	
	public TreeNode appendRight(int d){
		this.right = new TreeNode(d);
		return this.right;
	}

	public TreeNode appendLeft(int d){
		this.left = new TreeNode(d);
		return this.left;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public TreeNode getLeft() {
		return left;
	}

	public void setLeft(TreeNode left) {
		this.left = left;
	}

	public TreeNode getRight() {
		return right;
	}

	public void setRight(TreeNode right) {
		this.right = right;
	}
	
	public Boolean IsVisited() {
		return isVisited;
	}

	public void setIsVisited(Boolean isVisited) {
		this.isVisited = isVisited;
	}

	public static void print(TreeNode node){		
		
		if(node!= null){
			print(node.left);
			System.out.print(node.data+ " ");
			print(node.right);
		}
	}
}

******

Next the code to find the paths

package trees;

import java.util.Stack;

/**
 * Given a binary tree and 3 nodes x,y,z, write a function which returns true if
 * y lies in the path between x and z and false otherwise.
 * 
 * Example:
 * 
 *         1
 *        / \
 *       2   3
 *      /\   /\
 *     4  5 6  7
 *       /
 *      8 
 * 
 * Paths to consider are 124,1258,136,137. find if each of the distinct paths has
 * the nodes x,y,z satisfying the condition that y should be in between x and z
 * 
 * We use a stack to hold the intermediate paths -> O(n) space
 * 
 * 
 * @author sriniatiisc
 * 
 */
public class FindAPathContainingThreeNodes {

	public static void main(String[] args) {
		TreeNode r = getTree();
		String path1 = findPath(r,2,5,8);
		if (path1 != null) {
			System.out.println(path1);
		} else {
			System.out.println("No such path exists");
		}		
	}

	private static String findPath(TreeNode r, int x, int y, int z) {
		if (r == null)
			return null;
		Stack<TreeNode> nodes = new Stack<>();
		nodes.push(r);
		String path = "";

		TreeNode n1 = r; 
		while (n1 != null && !n1.IsVisited()) {
			if (n1.getLeft() != null && !n1.getLeft().IsVisited()) {
				path += new Integer(n1.getData());
				nodes.push(n1);
				n1 = n1.getLeft();
			} else if (n1.getRight() != null && !n1.getRight().IsVisited()) {
				path += new Integer(n1.getData());
				nodes.push(n1);
				n1 = n1.getRight();
			} else {
				if (!n1.IsVisited()) {
					String pathToSearch = path + new Integer(n1.getData());
					// find if the path contains x,y,z
					int xindex = find(pathToSearch, x);
					int yindex = find(pathToSearch, y);
					int zindex = find(pathToSearch, z);
					if (yindex > xindex && yindex < zindex) {
						return pathToSearch;
					}
					n1.setIsVisited(true);
				}
				n1 = nodes.pop();
				// remove the last character
				if (path.length() >= 1) {
					path = path.substring(0, path.length() - 1);
				} else{
					path = "";
				}

			}
		}
		return null;

	}

	private static int find(String path, int x) {
		return path.indexOf(new Integer(x) + "");
	}

	private static TreeNode getTree() {
		TreeNode root = new TreeNode(1);

		root.appendLeft(2).appendLeft(4);
		root.getLeft().appendRight(5).appendLeft(8);

		root.appendRight(3).appendLeft(6);
		root.getRight().appendRight(7);
		return root;
	}
}

The solution requires to identify if Y lies in path.
Here is an approach back track tree to find the LCA of node X and Z . If it is Y then return True else it is always false.

Public  Node BTNode (Node N, Node X, Node Z)
{ 
  If (!N) return;
  If(N==X || N==Z) Return N;
   
 Node L = BTNode(N.Left,X,Z); 
 Node R = BTNode(N.Right,X,Z);
  if (L&& R) return N;
  return L?L:R;
}

Below solution works for sure:









Remember, in a tree unique path exists between 2 nodes.
There are 2 use cases to it:
1) LCA of given 2 nodes ‘X’ and ‘Z’ is a 3rd node ‘C’;
find if a path exists from ‘Y’ down to either ‘X’ or ‘Z’ – return true, else false;
2) LCA of given 2 nodes ‘X’ and ‘Y’ is a either of ‘X’, ‘Y’;
Let LCA=’X’;
find if a path exists from ‘Y’ down to ‘Z’ – return true, else false;

For finding distance we can use BFS for efficient solution.

Find the LCA of x and z. Let it be P. Traverse the tree from P to find x and store the path by explicitly maintaining a stack. Check if y is in the stack or not. If yes return true, else do the same for the path between P and z. If y is present return true else return false.