Google Interview Question for SDE1s


Country: United States




Comment hidden because of low score. Click to expand.
6
of 8 vote

Do this in 3 parts:
-print the left outline (without the leaf element)
-print the leafs
-print the right outline

void print_left(Node *node) {
	if(node == null)
		return;
	if (node -> left != NULL || node->right != NULL)
		printf("%d ", node->v);
	print_left(node->left);
}

void print_right(Node *node, bool first) {
	if(node == null)
		return;

	print_right(node->rignt, false);
	if (first == false && (node -> left != NULL || node->right != NULL))
		printf("%d ", node->v);
}

void print_leafs(Node *node) {
	if (node == NULL)
		return;
	if (node->left == NULL && node->right == NULL) {
		printf("%d ", node->v);
	}
	print_leafs(node->left);
	print_leafs(node->right);
}

void print_outline(Node *root) {
	print_left(root);
	print_leafs(root);
	print_right(root, true);
}

Complexity time and memory:
Let the number of node in the tree be N:
print_left: O(logn), Memory for recursive stack: O(logn)
print_right: O(logn), Memory for recursive stack: O(logn)
print_deafs: O(n), Memory for recursive stack: O(logn)

... then the general time and memory complexity is:
print_outline: O(n) and O(logn)

- thiago.xth1 June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi,
I have a doubt in your explanation in time and space complexity.
We can not say it is logn because it completely depends on the structure of binary tree.
I mean If it is left or right skew tree then the time complexity is O(n), because we need traverse each and every node in this case.
If I am wrong please let me know
Thanks

- Srinivas June 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Srinivas

As per question the tree is completely binary tree so its right

if the tree is not completely binary tree then code will fail but its written as per problem statement

- Kavita June 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Thanks Bro.
and instead of passing boolean value pass root.right as a parameter
what do u say?

- Srinivas June 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

package com.cnu.ds;

public class BinaryTree {
	public static void main(String[] args) {

		// Level 0
		BinaryTreeNode<Character> treeNode = new BinaryTreeNode<>();
		treeNode.t = 'A';

		// Level 1
		treeNode.left = new BinaryTreeNode<>();
		treeNode.left.t = 'B';
		treeNode.right = new BinaryTreeNode<>();
		treeNode.right.t = 'C';

		// Level 2
		treeNode.left.left = new BinaryTreeNode<>();
		treeNode.left.left.t = 'D';
		treeNode.left.right = new BinaryTreeNode<>();
		treeNode.left.right.t = 'E';

		treeNode.right.left = new BinaryTreeNode<>();
		treeNode.right.left.t = 'F';
		treeNode.right.right = new BinaryTreeNode<>();
		treeNode.right.right.t = 'G';

		// Level 3
		treeNode.left.left.left = new BinaryTreeNode<>();
		treeNode.left.left.left.t = 'H';
		treeNode.left.left.right = new BinaryTreeNode<>();
		treeNode.left.left.right.t = 'I';

		treeNode.left.right.left = new BinaryTreeNode<>();
		treeNode.left.right.left.t = 'J';

		// Three parts
		// traversing left part
		// traversing leaves part
		// traversing right part
		printLeftPart(treeNode);
		printLeaves(treeNode);
		printRightPart(treeNode.right);
	}

	public static void printLeftPart(BinaryTreeNode<Character> root) {
		if (root.left != null) {
			System.out.print(root.t + " ");
			printLeftPart(root.left);
		}
	}

	public static void printLeaves(BinaryTreeNode<Character> root) {
		if (root != null) {
			if (root.left == null && root.right == null) {
				System.out.print(root.t + " ");
			}
			printLeaves(root.left);
			printLeaves(root.right);
		}
	}

	public static void printRightPart(BinaryTreeNode<Character> root) {
		if (root.right != null) {
			printLeftPart(root.right);
			System.out.print(root.t + " ");
		}
	}
}

- srinivas June 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

binary tree node

package com.cnu.ds;

public class BinaryTreeNode<T> {
	T t;
	BinaryTreeNode<T> left, right;

	public BinaryTreeNode() {
	}

	public BinaryTreeNode(T t, BinaryTreeNode<T> left, BinaryTreeNode<T> right) {
		super();
		this.t = t;
		this.left = left;
		this.right = right;
	}

}

- Srinivas June 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

all you have to do is in order- traversal and keep watch the maximum, O(n) running time O(h) where n the items number and h the height of the tree and in this case which is logn since it is complete BT.

- Anonymous September 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

How are printing left outline, or right outline or even the leaf elements help you find the maximum??
This isn't a BST. Completeness is irrelevant information. To get the max in a BT you have to traverse all the elements. As the max can be anywhere, in center, left outline, leaf, anywhere.

My solution will be do a Breadth First Search, and keep track of the max value or the node with max value. Return that. Runtime would be O(n) considering traversing all elements, and Queue would at max be size O ( log n ) or O ( height ).

- Rushabh November 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Hi!

I think I solved this problem. I just keep track if I am on the left or right branch, and then make sure to print the left and bottom before the right side :)

Please let me know if there is any bug that I haven't seen. Might be the case.

Hope you find it useful!

void printAntiClockwise(Tree *t, bool pureLeft, bool pureRight){

			if (t == NULL) return;
			
			bool printed = false;

			if (pureLeft ||
				((t->left == NULL) && (t->right == NULL))){
				printf("%s", t->value.c_str());
				printed = true;
			}

			Tree::printAntiClockwise(t->left, pureLeft && true, false);

			Tree::printAntiClockwise(t->right, false, pureRight && true);

			if (pureRight && !pureLeft && !printed){
				printf("%s", t->value.c_str());

			}

		}

- santiagocasti June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I like the simplicity of this code and it seems to make sense. However, can you explain how pureLeft and pureRight are being updated? Are they passed in as true?

- hkomputer June 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dude. I have a quick question. As per requirements, we are supposed to print the outline elements and not the inner elements in the loop. When i run through your program, I am able to Print - ADHIJEFGC. Here, E should not be printed. Please correct me if i am wrong.

- deepak_gta June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@HK22793

The idea is that you call the function with pureLeft and pureRight true the first time. These values are going to continue to be true in the respective left and right "branches" of the tree, but false in any other one. I also like simple and short code :)

@deepak_gta

I think there might be some problem with your binary tree construction, cause as you can see in the algorithm you will arrive to E with pureLeft and pureRight equal to false. Therefore, for it to print the value of E both children have to be null, which is not the case since E has as left child the node J. Hope it helps you :)

Thanks for the comments.

- santiagocasti June 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

The information of "complete" tree seems to be unnecessary.

- jiangok2006 June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

to use the information of "complete",i suggest we could use a array to store all the elements .Then we do the following:
1) print element with index of 1,2,4,...,k(k<=n)
2) print element with index of k+1,....,n,n/2 +1,n/2 +2,...,k-1
3) print element with index of n/2, n/4 ,...,1(not included)
please point out if i am wrong.

- roylee July 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

How about complexity O(n) because you have to check every position and memory O(h) where h is the height of the tree:

class Node{
  int val;
  Node left;
  Node right;
}

public int getMax(Node node){
  Stack<Node> history = new Stack<Node>();
  history.push(node);
  int max =  Integer.MIN_VALUE;
  while(history.hasNext()){
    Node temp = history.pop();
    if(temp.value > max){
      max = temp.value;
    }
    if(temp.right != null){
      history.push(temp.right);
    }
    if(temp.left != null){
      history.push(temp.left);
    };
  }
  return max;
}

- zortlord September 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I dont see why people are talking of printing the tree. The question says find the max in a BT, its unusually simple question, you just have to examine every node since its not a search tree.

- james.porcelli@stonybrook.edu September 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't get it either. I understand everyone is printing the whole tree, but why? why not just return the value at that node and compare it with a specified max value would do it.

- sid78669 October 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//print boundary travesal for a BT
//Boundry travesal = left view + leaf view + right view 
//NoteL- Do not include root two time and left view should be moving from
//root to leaf and right view should be moving from leaf to root

#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
#include<stack>
using namespace std;


struct Node
{
  int data;
  Node *left;
  Node *right;

  public:
  Node(int d = 0, Node * l = NULL, Node * r = NULL): data(d),left(l),right(r)
  {

  }
};

int Max(int i, int j)
{
   return i > j ? i : j;
}
void Insert(Node **root, int d)
{
   if(*root == NULL)
   {
      *root = new Node(d);
      return;
   }

   Node* temp = *root;

  if(temp->data > d)
  {
    Insert(&(temp->left),d);
  }
  else if(temp->data < d)
  {
    Insert(&(temp->right),d);
  }
  else//To allow duplicate keys do not return from here
  {
    //return;//Already present key
     //Insert(&(temp->right),d);
  }
}


int Height(Node* root)
{
   if(root == NULL)
   {
     return 0;
   }

   return 1 +Max(Height(root->left),Height(root->right));
}

void PrintLeftView(Node* root,int *p, int level)
{
   if(root == NULL) return;

   if(p[level] == INT_MAX &&(root->left != NULL || root->right != NULL))
   {
       p[level] = root->data;
   }

   PrintLeftView(root->left,p,level+1);
   PrintLeftView(root->right,p,level+1);
   
}


void PrintLeafsLeftToRight(Node* root)
{
   if(root == NULL) return;

   PrintLeafsLeftToRight(root->left);

   if(root->left == NULL && root->right == NULL)
   cout<<root->data<<" ";

   PrintLeafsLeftToRight(root->right);
}

void PrintRightView(Node* root,int* p, int level)
{
   if(root == NULL) return;
   
   if(p[level] == INT_MAX &&(root->left != NULL || root->right != NULL))
   {
       p[level] = root->data;
   }

   PrintRightView(root->right,p,level+1);
   PrintRightView(root->left,p,level+1);
  
}


void BoundryViewUtil(Node* root)
{
   int h = Height(root);

   int* p = new int[h-1];
   
   //Do not use memset here i done this mistake
 
   for(int i = 0; i < h-1;i++)
   p[i] = INT_MAX;

   PrintLeftView(root,p,0);
   for(int i = 0; i < h-1; i++)
   {
       cout<<p[i]<<"  ";
   }

   
   PrintLeafsLeftToRight(root);
   

   for(int i = 0; i < h-1;i++)
   p[i] = INT_MAX;

   PrintRightView(root,p,0);
   for(int i = h-2; i > 0; i--)//root already included with left so i > 0
   {
       cout<<p[i]<<"  ";
   }
   
   delete []p;//clean memory 
}
int main()
{
   Node *root1 = NULL;
   Insert(&root1,12);
   Insert(&root1,18);
   Insert(&root1,7);
   Insert(&root1,9);
   Insert(&root1,11);
   Insert(&root1,13);
   Insert(&root1,17);
   Insert(&root1,19);
   Insert(&root1,21);
   Insert(&root1,23);

   BoundryViewUtil(root1);

   return 0;
}

- Kavita June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,

It was really a nice part of explanation , conveyed by you.

Thanks..
:)

- Anonymous June 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
#include<stack>
using namespace std;


struct Node
{
  int data;
  Node *left;
  Node *right;

  public:
  Node(int d = 0, Node * l = NULL, Node * r = NULL): data(d),left(l),right(r)
  {

  }
};

void Insert(Node **root, int d)
{
   if(*root == NULL)
   {
      *root = new Node(d);
      return;
   }

   Node* temp = *root;

  if(temp->data > d)
  {
    Insert(&(temp->left),d);
  }
  else if(temp->data < d)
  {
    Insert(&(temp->right),d);
  }
  else//To allow duplicate keys do not return from here
  {
    //return;//Already present key
     //Insert(&(temp->right),d);
  }
}

void BoundryTravesalUsingOneLoop(Node *root,bool pureLeft,bool pureRight)
{

    bool isPrinted = false;
  
    if(root == NULL)
    return;

    if(root->left == NULL && root->right == NULL)
    {
        if(isPrinted == false)
        {
           cout<<root->data<<"  ";
           isPrinted = true;
        }
        return;
    }
    
    if(pureLeft && (!pureRight) && isPrinted == false)
    {
        cout<<root->data<<"  ";
        isPrinted  = true;
    }
     
     BoundryTravesalUsingOneLoop(root->left,pureLeft,false);
     BoundryTravesalUsingOneLoop(root->right,false,pureRight);

     if(pureRight && (!pureLeft) && isPrinted == false)
     {
         cout<<root->data<<"  ";
         isPrinted  = true;
     }
        

}
int main()
{
  

   Node *root2 = NULL;
   Insert(&root2,40);
   Insert(&root2,20);
   Insert(&root2,60);
   Insert(&root2,10);
   Insert(&root2,30);
   Insert(&root2,50);
   Insert(&root2,70);
   Insert(&root2,5);
   Insert(&root2,15);
   Insert(&root2,25);
   Insert(&root2,45);
   Insert(&root2,55);
   Insert(&root2,65);
   Insert(&root2,75);
   Insert(&root2,4);
   Insert(&root2,6);
   Insert(&root2,14);
   Insert(&root2,16);
   Insert(&root2,24);
   // Call function with both flags as true
   // if u put left falg as false left view will not get printed
   //if u put right flag as false right view will not get printed
   BoundryTravesalUsingOneLoop(root2,true,true);

   return 0;
}

- Kavita June 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n)

public class PrintTree {
	public static void main(String[] args) {
		Node a = new Node("A");
		Node b = new Node("B");
		Node c = new Node("C");
		Node d = new Node("D");
		Node e = new Node("E");
		Node f = new Node("F");
		Node g = new Node("G");
		Node h = new Node("H");
		Node i = new Node("I");
		Node j = new Node("J");
		
		a.left = b;
		a.right = c;
		b.left = d;
		b.right = e;
		c.left = f;
		c.right = g;
		d.left = h;
		d.right = i;
		e.left = j;

		a.print(0,0);
	}
}
 class Node{
	String name;
	public Node left;
	public Node right;
	public Node(String name){
		this.name = name;
	}

	
	public void print(int lcount, int rcount){		
		if (rcount == 0)
			System.out.println(name);
		if (left == null && right == null && rcount >0 && lcount >0)
			System.out.println(name);
		if (left != null)
			left.print(lcount +1,rcount);
		if (right != null)
			right.print(lcount,rcount +1 );
		if (lcount ==0 && rcount >0)
			System.out.println(name );
	}
	
}

- Gman June 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Your solution looks good but i think its loosing some edge cases in printLeft and printRight function consider the case where the tree is like this:
a
/ \
b c
\ /
d e
/ \ / \
f gh i
would it take into account printing the node with value d and node with value e as you are always recursing left in printLeft without checking that if left node is null we should call printLeft(node->right); and similary in printRight if the right node is null we should call PrintRight(node->left);

- shawn June 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the Sample Code for Tree Outline:


public class Treeoutline {

/**
* @param args
*/

char data;
Treeoutline left;
Treeoutline right;

public Treeoutline(char ch)
{
this.data = ch;
this.left = null;
this.right = null;
}

public static void printLeaves(Treeoutline root)
{
if(root == null)
return;
if(root.left==null && root.right==null)
System.out.print(root.data+ " ");

printLeaves(root.left);
printLeaves(root.right);
}

public static void printLeft(Treeoutline root)
{
if(root==null)
return;
if(!(root.left==null&&root.right==null))
System.out.print(root.data+" ");
if(root.left== null)
printLeft(root.right);
printLeft(root.left);

}

public static void printRight(Treeoutline root)
{
if(root==null)
return;
if(root.right== null)
printRight(root.left);
else
printRight(root.right);
if(!(root.left==null&&root.right==null))
System.out.print(root.data+" ");

}

public static void main(String[] args) {
// TODO Auto-generated method stub

Treeoutline root = new Treeoutline('a');
root.left = new Treeoutline('b');
root.right = new Treeoutline('c');
root.left.right = new Treeoutline('d');
root.right.left = new Treeoutline('e');
root.left.right.left = new Treeoutline('f');
root.left.right.right =new Treeoutline('g');
root.right.left.left = new Treeoutline('h');
root.right.left.right = new Treeoutline('i');
root.right.left.right.left = new Treeoutline('j');
root.right.left.right.right = new Treeoutline('k');


System.out.println("Printing the Outline of the Tree");
Treeoutline.printLeft(root);
Treeoutline.printLeaves(root);
Treeoutline.printRight(root);


}

}

- shawn June 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Treeoutline {

	/**
	 * @param args
	 */
	
	char data;
	Treeoutline left;
	Treeoutline right;
	
	public Treeoutline(char ch)
	{
		this.data = ch;
		this.left = null;
		this.right = null;
	}
	
	public static void printLeaves(Treeoutline root)
	{
		if(root == null)
			return;
		if(root.left==null && root.right==null)
			System.out.print(root.data+ " ");

			printLeaves(root.left);
			printLeaves(root.right);
	}
	
	public static void printLeft(Treeoutline root)
	{
		if(root==null)
			return;
		if(!(root.left==null&&root.right==null))
		System.out.print(root.data+" ");
		if(root.left== null)
			printLeft(root.right);
		printLeft(root.left);
		
	}
	
	public static void printRight(Treeoutline root)
	{
		if(root==null)
			return;
		if(root.right== null)
			printRight(root.left);
		else
		printRight(root.right);
		if(!(root.left==null&&root.right==null))
		System.out.print(root.data+" ");
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Treeoutline root = new Treeoutline('a');
		root.left = new Treeoutline('b');
		root.right = new Treeoutline('c');
		root.left.right = new Treeoutline('d');
		root.right.left = new Treeoutline('e');
		root.left.right.left = new Treeoutline('f');
		root.left.right.right =new Treeoutline('g');
		root.right.left.left = new Treeoutline('h');
		root.right.left.right = new Treeoutline('i');
		root.right.left.right.left = new Treeoutline('j');
		root.right.left.right.right = new Treeoutline('k');
		
		
		System.out.println("Printing the Outline of the Tree");
		Treeoutline.printLeft(root);
		Treeoutline.printLeaves(root);
		Treeoutline.printRight(root);
		
		
	}

}

- Anonymous June 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in one tree traversal pass by changing traversal state, but you need to find out right-most leaf node ahead of time to do the second traversal state change.

{

public class TreeWalker {
private enum Phase { left, leaf, right};
private TreeNode root;
private TreeNode rightMostNode;
private Phase phase = Phase.left;
public TreeWalker(TreeNode r) {
this.root = r;
this.rightMostNode = getRightMostNode(r);
walk(r);
}

private boolean isLeaf(TreeNode n) {
return n.getLeft() == null && n.getRight() == null;
}

private TreeNode getRightMostNode(TreeNode n) {
if (n == null) return null;
while (!isLeaf(n)) {
n = n.getRight();
}
return n;
}

private void walk(TreeNode node) {
if (node == null) return;
if (phase == Phase.left) {
System.out.println(node);
if (isLeaf(node)) {
phase = Phase.leaf;
}
} else if (phase == Phase.leaf) {
if (isLeaf(node)) {
if (node == rightMostNode) {
phase = Phase.right;
} else {
System.out.println(node);
}
}
}

walk(node.getLeft());
walk(node.getRight());
if (phase == Phase.right && node != root) {
System.out.println(node);
}
}


public static void main(String[] args) {
TreeNode a = new TreeNode('A');
TreeNode b = new TreeNode('B');
TreeNode c = new TreeNode('C');
TreeNode d = new TreeNode('D');
TreeNode e = new TreeNode('E');
TreeNode f = new TreeNode('F');
TreeNode g = new TreeNode('G');
TreeNode h = new TreeNode('H');
TreeNode i = new TreeNode('I');
TreeNode j = new TreeNode('J');

a.setLeft(b);
a.setRight(c);
b.setLeft(d);
b.setRight(e);
d.setLeft(h);
d.setRight(i);
e.setLeft(j);
c.setLeft(f);
c.setRight(g);

new TreeWalker(a);
}
}













}

- acton July 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in one tree traversal pass by changing traversal state, but you need to find out right-most leaf node ahead of time to do the second traversal state change.

{

public class TreeWalker {
private enum Phase { left, leaf, right};
private TreeNode root;
private TreeNode rightMostNode;
private Phase phase = Phase.left;
public TreeWalker(TreeNode r) {
this.root = r;
this.rightMostNode = getRightMostNode(r);
walk(r);
}

private boolean isLeaf(TreeNode n) {
return n.getLeft() == null && n.getRight() == null;
}

private TreeNode getRightMostNode(TreeNode n) {
if (n == null) return null;
while (!isLeaf(n)) {
n = n.getRight();
}
return n;
}

private void walk(TreeNode node) {
if (node == null) return;
if (phase == Phase.left) {
System.out.println(node);
if (isLeaf(node)) {
phase = Phase.leaf;
}
} else if (phase == Phase.leaf) {
if (isLeaf(node)) {
if (node == rightMostNode) {
phase = Phase.right;
} else {
System.out.println(node);
}
}
}

walk(node.getLeft());
walk(node.getRight());
if (phase == Phase.right && node != root) {
System.out.println(node);
}
}


public static void main(String[] args) {
TreeNode a = new TreeNode('A');
TreeNode b = new TreeNode('B');
TreeNode c = new TreeNode('C');
TreeNode d = new TreeNode('D');
TreeNode e = new TreeNode('E');
TreeNode f = new TreeNode('F');
TreeNode g = new TreeNode('G');
TreeNode h = new TreeNode('H');
TreeNode i = new TreeNode('I');
TreeNode j = new TreeNode('J');

a.setLeft(b);
a.setRight(c);
b.setLeft(d);
b.setRight(e);
d.setLeft(h);
d.setRight(i);
e.setLeft(j);
c.setLeft(f);
c.setRight(g);

new TreeWalker(a);
}
}













}

- acton July 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey

Just two line Of Solution...

1) Find All Nodes At same Height Of Tree
2) If Height=Leaf Then Return all
Else Return Front And Last From All Heights

- Brijesh Patel August 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well this isn't a binary search tree, just a binary tree. As a result the only way to do this is to more or less do a traversal and keep track of the maximum element to that point. So it'll be O(n) time. That being said, if it's a BST, then it's even easier, simply trace the right pointer till you hit a null and that'll be your max element.

- Sagar August 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree, I find it hard to understand why people are posting all these complex solutions here.

- Anonymous September 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

shouldn't simple inorder work ?

int inorder(Node root)
{
if(root == null) return -1;
  int l,r;
  if(root.left != null) l = inorder(root.left);
  if(root.right != null) r = inorder(root.right);
  return Math.max(Math.max(l,r), root.value);
}

- aditya.eagle059 January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static class Node{
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }
    public static int maxValue(Node root){
        if (root == null)
            return Integer.MIN_VALUE;
        return Math.max(root.value,Math.max(maxValue(root.right), maxValue(root.left)));
    }
    public static void main(String[] args){
        Node root = new Node(5);
        Node node2 = new Node(6);
        Node node3 = new Node(9);
        Node node4 = new Node(78);
        Node node5 = new Node(4);
        Node node6 = new Node(90);
        root.left = node2;
        root.right = node5;
        node2.right = node4;
        node4.left = node3;
        node2.left = node6;
        System.out.println(maxValue(root));
        // 90
    }

- kameldabwan March 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not just keep track of the max element?

Python

def findMax(node, maxi):

	if node == None:
		return maxi 

	return max(findMax(node.left, maxi), findMax(node.right,maxi), node.value )

- Leon March 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<process.h>
#include<stdlib.h>
typedef struct node
{
	int data;
	struct node*lptr;
	struct node*rptr;
}node;
int big;
node*create()
{
	node*temp;
	int val;
	char ch;
	temp=(node*)malloc(sizeof(node));
	if(temp==NULL)
	{
		printf("memory allocation failure");
	}
	else
	{
		printf("enter value u want\n");
		scanf("%d",&val);
		temp->data=val;
		temp->lptr=NULL;
		temp->rptr=NULL;
		printf("do u want to insert node at %d left\n",temp->data);
		fflush(stdin);
		scanf("%c",&ch);
		if(ch=='y')
		temp->lptr=create();
		printf("do u want to insert node at %d  right\n",temp->data);
		fflush(stdin);
		scanf("%c",&ch);
		if(ch=='y')
		temp->rptr=create();
		return(temp);
	}
}
int inorder(node*temp)
{
	if(temp!=NULL)
	{
		if(temp->data>big)
		big=temp->data;
		inorder(temp->lptr);
		printf("%d\t",temp->data);
		inorder(temp->rptr);
	}
	return(big);
}
int main()
{
		node*temp;
	int x;
	temp=create();
	big=temp->data;
	x=inorder(temp);
	printf("\n\nbiggest element is %d",x);
	return 0;
}

- apoorva November 15, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More