Google Interview Question
SDE1sCountry: United States
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
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
Thanks Bro.
and instead of passing boolean value pass root.right as a parameter
what do u say?
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 + " ");
}
}
}
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;
}
}
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.
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 ).
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());
}
}
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?
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.
@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.
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.
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;
}
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.
//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;
}
#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;
}
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 );
}
}
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);
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);
}
}
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);
}
}
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);
}
}
}
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);
}
}
}
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.
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
}
#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;
}
Do this in 3 parts:
-print the left outline (without the leaf element)
-print the leafs
-print the right outline
Complexity time and memory:
- thiago.xth1 June 18, 2014Let 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)