CareerCup

f(t,0);
int f(tree *t,int cnt)
{
if(!t) return cnt;
else if(t->data)
{
cnt++;
cl = f(t->left);
cr = f(t->right);
return max(cl,cr);
}
else
return cnt;
}

int f(node * t) {
if(!t) return 0;
if(t->data==0) return 0;
else {
int leftdepth =f(t->left);
int rightdepth = f(t->right);
if(leftdepth>rightdepth)
return leftdepth +1;
else
return rightdepth+1;
}
}

public static int checkDeepestOne(BinaryTreeNode node){
if(node == null){
return 0;
}

if(node.element.compareTo(1) == 0){
return 1 + Math.max(checkDeepestOne(node.left),checkDeepestOne(node.right));
}
else{
return 0;
}
}

@All above,
Please follow the question correctly.. Question is related to finding "PATH" and you all people are just trying to find position(depth) of deepest 1.

Do the BFS and find the required deepest Node Pointer.

If Once you found the deepest node then find the path between root to deepest Node.

void findPath(Node root, Node node){
Stack->push(root);
if(node == root){
print stack data;

return;
}
if(root->left != null){
findPath(root->left, node);
}
if(root->right!=null){
findPath(root.right, node);
}
Stack->pop();
}

int path_depth(node *cur)
{
if(cur == NULL)
{
return 0;
}
if(cur->data ==0)
{
return 0;
}
if(cur->data == 1)
{
return max(path_depth(cur->left), path_depth(cur->right)) + 1;
}
}

void print_path(node *cur)
{
if(cur == root && root->data == 1)
{
print(root->data);
}
if(cur->data == 0)
{
return;
}
if(cur->left && cur->right)
{
if(path_depth(cur->left) > path_depth(cur->right))
{
print_path(cur->left);
}
if(path_depth(cur->left) < path_depth(cur->right))
{
print_path(cur->right);
}
if(path_depth(cur->left) == path_depth(cur->right) && path_depth(cur->left) == 0)
{
return;
}
else
{
print_path(cur->right);
}
}
else if(cur->left)
{
print_path(cur->left);
}
else if(cur->right)
{
print_path(cur->right);
}
else
{
return;
}
}


Please correct me if you think I was wrong or this is too complicated. Thanks.

@aammgg didn't check you approach, but the idea might work. As a matter of fact using dynamic programing approach we could do less calculations, but as usual memory vs. loops... Bellow code could be optimized e.g. by removing new Stack for cases where allocation doesn't make sense etc. Please let me know your thoughts. here's my solution:

{{
static Stack FindPath(TreeNode root)
{
Stack stack = new Stack();
if (root != null && root.Value == 1)
{
Stack left = FindPath(root.Left);
Stack right = FindPath(root.Right);

if (left.Count > right.Count)
{
stack = left;
}
else
{
stack = right;
}

stack.Push(root);
}

return stack;
}

-- print
Stack st = FindPath(node);

while (st.Count > 0)
{
// print some name, printing 1s doesn't make sense...
Console.WriteLine(((TreeNode)st.Pop()).Name);
}
}}

It is easy to solve this if the path is not required. But if path is required it becomes little more complex.

public List<BinaryNode> FindPathToDeepest1Node(BinaryNode startNode)
        {
            if (null == startNode)
            {
                return null;
            }

            List<BinaryNode> deepest1Path = new List<BinaryNode>();
            int pathLen = FindPathToDeepest1NodeRecur(startNode, ref deepest1Path);
            Console.WriteLine("Path length of the longest path with 1's is {0}", pathLen);
            return deepest1Path;
        }

        private int FindPathToDeepest1NodeRecur(BinaryNode startNode, ref List<BinaryNode> deepest1Path)
        {
            int pathLen = 0;
            if (null == startNode || startNode.Value == BinValue.Zero)
            {
                return pathLen;
            }

            deepest1Path.Add(startNode);
            pathLen++;

            List<BinaryNode> deepest1PathLeft = new List<BinaryNode>();
            int deepestLenInLeftSubTree = FindPathToDeepest1NodeRecur(startNode.Left, ref deepest1PathLeft);

            List<BinaryNode> deepest1PathRight = new List<BinaryNode>();
            int deepestLenInRightSubTree = FindPathToDeepest1NodeRecur(startNode.Right, ref deepest1PathRight);

            if (deepestLenInLeftSubTree >= deepestLenInRightSubTree)
            {
                deepest1Path.AddRange(deepest1PathLeft);
                pathLen += deepestLenInLeftSubTree;
            }
            else
            {
                deepest1Path.AddRange(deepest1PathRight);
                pathLen += deepestLenInRightSubTree;
            }

            return pathLen;
        }

// Call following method with currCount = 0 ; maxCount = 0;
// After method returns print 1  maxCount times.

public void DeepestOnePath(treeNode curr, int currCount, ref int maxCount) //Method
{
    if (curr == null || curr.value == 0)
        return;

    currCount++;

    // if a leaf Node
    if (curr.rightChild == null && curr.leftChild == null)
    {
        if (maxCount < currCount)
            maxCount = currCount;
                    
        return;
    }

    DeepestOnePath(curr.leftChild, currCount, ref maxCount);
    DeepestOnePath(curr.rightChild, currCount, ref maxCount);
}

template <typename T>
string deepest1(struct BTNode<T>* t) {
  if (t != NULL) {
    if (isLeaf(t)) return "";
    if (t->data == 1) {
      string l = deepest1(t->left);
      string r = deepest1(t->right);
      if (l.length() > r.length()) {
        if (t->left != NULL && t->left->data == 1) return "l"+l;
        return l;
      }
      else {
        if (t->right != NULL && t->right->data == 1) return "r"+r;
        return r;
      }
    }
  }
  return "";
}

public static Stack<Node> FindMaximumDepthOfNode(Node inputNode)
{
Stack<Node> retPath = new Stack<Node>();

if(inputNode != null && inputNode.data != 0)
{
Stack<Node> leftPath, rightPath;

leftPath = FindMaximumDepthOfNode(inputNode.leftNode);
rightPath = FindMaximumDepthOfNode(inputNode.rightNode);

if (leftPath.Count >= rightPath.Count)
{
retPath = leftPath;
}
else
{
retPath = rightPath;
}

Node currentNode = inputNode;
currentNode.leftNode = null;
currentNode.rightNode = null;
retPath.Push(inputNode);
}

return retPath;
}

public static Stack<Node> FindMaximumDepthOfNode(Node inputNode)
{
Stack<Node> retPath = new Stack<Node>();

if(inputNode != null && inputNode.data != 0)
{
Stack<Node> leftPath, rightPath;

leftPath = FindMaximumDepthOfNode(inputNode.leftNode);
rightPath = FindMaximumDepthOfNode(inputNode.rightNode);

if (leftPath.Count >= rightPath.Count)
{
retPath = leftPath;
}
else
{
retPath = rightPath;
}

Node currentNode = inputNode;
currentNode.leftNode = null;
currentNode.rightNode = null;
retPath.Push(inputNode);
}

return retPath;
}

Here is a solution from my side. Please let me know your views,

static int count = 0;
Stack S = new Stack();

void deepestNode(Node * root)
{
if(root == null)
return;
if(root.data == 1)
root.data = count;
s.Push(root);
count++;
deepestNode(root->left);
deepestNode(root->right);
}

The stack can then be checked for the deepest level node in the tree. The path of which can be determined from the tree again. Traversal log(n)

Is everyone over thinking, or am I missing something here ?

List<Node> depth(Node p, List<Node> nodePath)
{
	if(p==NULL || p.left().value != 1)return nodePath ;
	
	nodePath.add(p);   
   
	List<Node> left = depth(p.left());
	List<Node> right = depth(p.right());
	
	if (left.size() > right.size())
		return left;
	else 
		return right;
}

Simple and neat solution...

void printLongestPathWithOnes(node* root, int cpath[], int clen, int mpath[], int &mlen)
{
	if(!root || !root->data)
		return;

	cpath[clen++] = root->data;

	if(clen > mlen)
	{
		mlen = clen;
		for(int i = 0; i < mlen; i++)
			mpath[i] = cpath[i];
	}

	printLongestPathWithOnes(root->left, cpath, clen, mpath, mlen);
	printLongestPathWithOnes(root->right, cpath, clen, mpath, mlen);
}

'

and 1=

' and 1=

\'

'''

ookjk85h74

1 OR 1=1

1' OR '1'='1

1'1

' 1 AND 1=1

1 AND 1=1

1\'1

) or ('1'='1--

' or 1=1/*

' or 1=1--

order by 1000/*

order by 1000;--

' order by 1000/*

' order by 1000;--

' or 1=1--

" or 1=1--

') or ('a'='a

'

and 1=

' and 1=

\'

'''

ookjk85h74

1 OR 1=1

1' OR '1'='1

1'1

' 1 AND 1=1

1 AND 1=1

1\'1

) or ('1'='1--

' or 1=1/*

' or 1=1--

order by 1000/*

order by 1000;--

' order by 1000/*

' order by 1000;--

' or 1=1--

" or 1=1--

') or ('a'='a

'

and 1=

' and 1=

\'

'''

ookjk85h74

1 OR 1=1

1' OR '1'='1

1'1

' 1 AND 1=1

1 AND 1=1

1\'1

) or ('1'='1--

' or 1=1/*

' or 1=1--

order by 1000/*

order by 1000;--

' order by 1000/*

' order by 1000;--

' or 1=1--

" or 1=1--

') or ('a'='a

public class DeepestOneInBinaryTree {

	class Node{
		int value;
		Node leftChild, rightChild;
		boolean isLeftChildOfRoot;
	}
	
	static int deepestOneInTree(Node root){
		if(root == null){
			return 0;
		}
		Stack<Node> pathFromRoot = new Stack<Node>();
		pathFromRoot.add(root);
		Node longestPathEndPoint;
		int maxLengthOfValidPath=0;
		int currentLengthOfValidPath=0;
		while(!pathFromRoot.empty()){
			Node currNode = pathFromRoot.peek();
			boolean doneProcessingNode = false;
			if(currNode.value == 1){
				currentLengthOfValidPath = pathFromRoot.size();
				if(currentLengthOfValidPath > maxLengthOfValidPath){
					maxLengthOfValidPath = currentLengthOfValidPath;
					longestPathEndPoint = currNode;
				}
				if(currNode.leftChild != null){
					pathFromRoot.push(currNode.leftChild);
					currNode.leftChild.isLeftChildOfRoot = true;
				} else if(currNode.rightChild != null){
					pathFromRoot.push(currNode.rightChild);
					currNode.rightChild.isLeftChildOfRoot = false;
				} else {
					doneProcessingNode = true;
				}
			} else {
				doneProcessingNode = true;
			}
			
			if(doneProcessingNode){
				pathFromRoot.pop();
				boolean stackInValidState = false;
				while(!stackInValidState){
					if(pathFromRoot.empty()){
						break;
					}
					Node parentOfCurrNode =  pathFromRoot.peek();
					if(currNode.isLeftChildOfRoot){
						if(parentOfCurrNode.rightChild != null){
							pathFromRoot.push(parentOfCurrNode.rightChild);
							stackInValidState = true;
						} else {
							currNode = pathFromRoot.pop();
						}
					}
				}
			}
		}
		return maxLengthOfValidPath;
	}
}

${@print(md5(google_bot))}

'

and 1=

' and 1=

\'

'''

ookjk85h74

1 OR 1=1

1' OR '1'='1

1'1

' 1 AND 1=1

1 AND 1=1

1\'1

) or ('1'='1--

' or 1=1/*

' or 1=1--

order by 1000/*

order by 1000;--

' order by 1000/*

' order by 1000;--

' or 1=1--

" or 1=1--

') or ('a'='a

${@print(md5(google_bot))}

'

and 1=

' and 1=

\'

'''

ookjk85h74

1 OR 1=1

1' OR '1'='1

1'1

' 1 AND 1=1

1 AND 1=1

1\'1

) or ('1'='1--

' or 1=1/*

' or 1=1--

order by 1000/*

order by 1000;--

' order by 1000/*

' order by 1000;--

' or 1=1--

" or 1=1--

') or ('a'='a

Simple Python solution:

a) Traverse left and right calculating count of 1s in path on both. Return max as the final count
b) Where 0 is encountered reset count for the path to 0 and return
c) When leaf is encountered return the count

def max_path(root, count):

  if not root:
    return count
  
  if root.val == 0:
    return 0
  else:
    count += 1

  count = max(max_path(root.left, count), max_path(root.right, count))

  return count

Simple Python solution:

a) Traverse left and right calculating count of 1s in path on both. Return max as the final count
b) Where 0 is encountered reset count for the path to 0 and return
c) When leaf is encountered return the count

def max_path(root, count):

  if not root:
    return count
  
  if root.val == 0:
    return 0
  else:
    count += 1

  count = max(max_path(root.left, count), max_path(root.right, count))

  return count

Simple Python solution:

a) Traverse left and right calculating count of 1s in path on both. Return max as the final count
b) Where 0 is encountered reset count for the path to 0 and return
c) When leaf is encountered return the count

def max_path(root, count):

  if not root:
    return count
  
  if root.val == 0:
    return 0
  else:
    count += 1

  count = max(max_path(root.left, count), max_path(root.right, count))

  return count

${@print(md5(google_bot))}

'

and 1=

' and 1=

\'

'''

ookjk85h74

1 OR 1=1

1' OR '1'='1

1'1

' 1 AND 1=1

1 AND 1=1

1\'1

) or ('1'='1--

' or 1=1/*

' or 1=1--

order by 1000/*

order by 1000;--

' order by 1000/*

' order by 1000;--

' or 1=1--

" or 1=1--

') or ('a'='a