Facebook Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
3
of 3 vote

Assuming the following structure of the binary tree

struct Node {
Node *left, *right; 
};

We can write a recursive function to calculate the maximum depth of a node:
First compute the maximum depth of the two child nodes and take the maximum out of them. This gives us the maximum depth of the children. Now we add 1 to it (for the current node) and this will be the maximum depth starting from the current node. We call the function with the root of the binary tree to get the maximum depth of the whole tree.

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

- Balajiganapathi S August 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yep that's what I thought as well: recursion. But what if recursion overhead is not acceptable for them?

- StrategicCoderForce September 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@StrategicCoderForce - I would be surprised to hear someone ask for this without recursion, but if so, I would say probably use a queue - at each node you visit, pull it out of the queue and add its children, and keep doing so until the queue is empty. Of course, you would need to keep track of the depth of each node, so you'd probably want a queue of QNode, where QNode is a struct containing a Node and a depth.

Not the most elegant solution, but like I said, I'd be surprised if they asked you to do this question without recursion.

I went ahead and wrote up some C++ code to test it:

#include <iostream>
#include <queue>

using namespace std;

struct Node
{
	Node *left, *right;
	char data;
	Node(char d) : left(NULL), right(NULL), data(d) {}
};

struct QNode
{
	Node *node;
	int depth;
	QNode(Node *n, int d) : node(n), depth(d) {}
};

int findMaxDepth(Node *head)
{
    queue<QNode> q;
    int depth = 1;
    int maxDepth = 0;
    QNode root(head, depth);
    q.push(root);
    while (!q.empty())
    {
        QNode n = q.front();
        if (n.depth > maxDepth)
        {
        	maxDepth = n.depth;
        }
        if (n.node->left != NULL)
        {
            QNode left(n.node->left, n.depth + 1);
            q.push(left);
        }
        if (n.node->right != NULL)
        {
            QNode right(n.node->right, n.depth + 1);
            q.push(right);
        }
        q.pop();
    }
    return maxDepth;
}

// Note: A-G represent a 3-level balanced binary tree, and H just hangs off to the right of G
int main()
{
	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');
	B->left = A;
	B->right = C;
	D->left = B;
	D->right = F;
	F->left = E;
	F->right = G;
	G->right = H;
	int max = findMaxDepth(D);
	cout << "Max depth = " << max << endl;
}

Here's what the tree looks like:
    D
 B     F
A C   E G
          H

- Nick January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public class BinaryTree {
  public final int data;
  public BinaryTree left = null;
  public BinaryTree right = null;

private static int solveRecursive(BinaryTree node) {
    return (node == null) ? 0 : 1 + Math.max(solveRecursive(node.left), solveRecursive(node.right));
  }

  private static int solveIterative(BinaryTree root) {
    if (root == null) {
      return 0;
    }

    int depth = 0;
    List<BinaryTree> current = Lists.newArrayList(root);

    while (!current.isEmpty()) {
      List<BinaryTree> next = Lists.newArrayList();
      for (BinaryTree node : current) {
        if (node.left != null) {
          next.add(node.left);
        }
        if (node.right != null) {
          next.add(node.right);
        }
      }
      depth++;
      current = Lists.newArrayList(next);
    }

    return depth;
  }
}

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

same as height of a binary tree...

int maxdepth(struct node *start)
{
return 1+max(maxdepth(start->left),maxdepth(start->right));
}

- rvndr August 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<?php

function maxDepth($node)
{
	if ($node === null) {
		return 0;
	}

	$left = maxDepth($node->left) + 1;
	$right = maxDepth($node->right) + 1;

	return $left > $right ? $left : $right;
}

- paul4156 August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//for no. of leaf node(NLN)
struct BTnode{
int data;
struct BTnode *lc;
struct BTnode *rc;
};
NLN(struct BTnode *s)
{
if (s==NULL)
return NULL;
else if(s->lc==NULL && s->rc==NULL)
return 1;
else
xl=NLN(s->lc);
xr=NLN(s->rc);
return (xl+xr);
}
struct BTnode{
int data;
struct BTnode *lc;
struct BTnode *rc;
};
struct BTnode *maxdepth(struct BTnode *s)
{
if(s==NULL);
return NULL;
else if(s->lc==NULL && s->rc==NULL)
{
return 0;
}
else
xl=NLN(s->lc);
xr=NLN(s->rc);
int c=max(xl,xr);
return c+1;
}

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

We can also optimize the time complexity to O(n) if we introduce a new field 'depth' to the node struct.

struct node {
  node *left, *right;
  int data, depth;
}node ;

We use the queue to traverse the tree in level order. Then update the maximum level of depth & child's depth on each node discover.

- Psycho September 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What's your next question?

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

//We can assume that we have a class Node with left and right properties
class Node{
	Node left;
	Node right;
	//Other properties..
}

class Pair{
	/*
	* A node
	*/
	public Node n;
	/*
	* Depth of the node in the binary Tree that belongs
	*/
	public int d;
	public Pair(Node _n, int _d){
		n=_n;
		d=_d;
	}
}

//Time complexity: O(n)  [n = number of nodes in the parameter tree]
//Space Complexity: O(n) [each node is stored only once into the stack, and each node is visited]
public static int MaxDepthBinaryTree(Node root){
	LinkedList<Pair> stack = new LinkedList<Pair>();
	if(root!=null){
		stack.push(root);
		int depth = 0;
	}
	while(!stack.isEmpty()){
		Pair pair= stack.pop();
		Node node = pair.n;
		if(node.left!=null){
			stack.push(new Pair(node.left,node.d+1));
		}
		if(node.right!=null){
			stack.push(new Pair(node.right,node.d+1));
		}
	}
}
public static void MaxDepthBinaryTree(Node root){
	return MaxDepthBTAux(root,0);
}

public static void MaxDepthBinaryTree(Node root, int currentDepth){
	if(root!=null)
		return Math.max(
						MaxDepthBinaryTree(root.left, currentDepth+1),
						MaxDepthBinaryTree(root.right, currentDepth+1)
						);
	}
	return currentDepth;
}

- German September 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java code , here you go
key is to compare the node which has both child

public class CMain {

	public static void main(String[] args){
       
		BinaryTree bt = new BinaryTree();
		
		bt.insert(11);
		bt.insert(5);
		bt.insert(6);
		bt.insert(9);
		bt.insert(10);
		bt.insert(15);
		bt.insert(3);
		
		bt.display();
		
		int max=bt.getMaxDepth(bt.root);
		System.out.println(max);
		
	}	
	
	}





public class BinaryTree {

	class Node{
		int data;
		Node leftChild;
		Node rightChild;
		
		public Node(int d){
			this.data=d;
		}
	}
	
	Node root;
	
	public void insert(int d){
		Node n=new Node(d);
		if(root==null){
			root=n;
		}
		else{		
			Node curr=root;
			Node parr=null;


			while(true){
				parr=curr;
				if(d<curr.data){
					curr=curr.leftChild;
					if(curr==null){
						parr.leftChild=n;
						return;
					}
				}
				else{
					curr=curr.rightChild;
					if(curr==null){
						parr.rightChild=n;
						return;
					}
				}			
			}
		}
		
	}
	
	public int getMaxDepth(Node n){
		Node curr=n;
		int count=0;
		if(curr!=null){
			count++;
			if(curr.leftChild!=null && curr.rightChild==null)
				return count+getMaxDepth(curr.leftChild);
			else if(curr.leftChild==null && curr.rightChild!=null) 
				return count+getMaxDepth(curr.rightChild);						
			else {
				if(getMaxDepth(curr.leftChild)>getMaxDepth(curr.rightChild))
					return count+getMaxDepth(curr.leftChild);
				else
					return count+getMaxDepth(curr.rightChild);
			}
		}
		else
			return count;
						
	}
	
	public void display(){
		Stack<Node> parr = new Stack<Node>();
		Stack<Node> curr = new Stack<Node>();
		boolean isEmptyRow=false;
		
		parr.push(root);
		
		while(isEmptyRow==false){
			isEmptyRow=true;
			while(parr.isEmpty()==false){
				Node n=(Node)parr.pop();
				if(n!=null){
					System.out.print("  "+n.data+"  ");
					curr.push(n.leftChild);
					curr.push(n.rightChild);
					
					if(n.leftChild!=null || n.rightChild!=null)
						isEmptyRow=false;
				}
				else{
					System.out.print("  **  ");
					curr.push(null);
					curr.push(null);
				}			
			}
			
			while(curr.isEmpty()==false){
				parr.push(curr.pop());
			}
			
			System.out.println("\r\n");
		}
		
		
	}
	
	
}

- Youngsam September 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java solution

import java.util.Random;
import java.util.Queue;
import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.lang.Math;

//Assuming that the root has depth of 0 and leafnodes have
//a depth of heght.
public class careerCup_Facebook_maximumDepth{
	
	public static Node generateTree(int n){
		Random rnd = new Random();

		if(n <= 0)		return null;

		Integer x = new Integer( Math.abs( rnd.nextInt()%(n*n) ) );

		Node <Integer> root= new Node<Integer>( x );
		Node <Integer> curr = root;

		for(int i = 1; i < n ; i++){
			boolean goLeft = rnd.nextBoolean();
			if(goLeft && curr.left == null){
				curr.<Integer>addLeft( new Integer( Math.abs( rnd.nextInt()%(n*n) ) ));
				curr = root;
				continue;
			}if(!goLeft && curr.right == null){
				curr.addRight( new Integer( Math.abs( rnd.nextInt()%(n*n) ) ) );
				curr = root;
				continue;
			}else{
				curr = root;
				while(curr.left != null || curr.right != null ){
					goLeft = rnd.nextBoolean();
					if( goLeft ){
						if( curr.left != null  ){
							curr = curr.left;
						}else{ //Else we might add a left child to this node.
							break;
						}
					}else{
						if( curr.right != null  ){
							curr = curr.right;
						}else{ //Else we might add a left child to this node.
							break;
						}
					}
				
				}
			}
			

		}

		return root;


	}

	/*Finds the maximum depth of a tree.
	* The depth of the root node is assumened to be 0.
	* The depth of a root node is the number of edges from the root.
	* The depth of a null tree is defined to be -1.
	*/
	public static int maxDepth(Node n){
		if(n == null )		return -1;

		IntWrapper dWrap = new IntWrapper(-1);		//TODO: IntWrapper Class
		_maxDepth( n , 0 , dWrap );
		return dWrap.val;

	}

	
	//Helper function.
	public static void _maxDepth(Node n, int d, IntWrapper dWrap){
		
		if( n == null)		return;

		//Has another deeper node been visited?
		if( d > dWrap.val ){
			dWrap.val = d;		//This is the deepest node seen so far.
		}

		//Go deeper. While there are more nodes to the left.
		if(n.left != null)
			_maxDepth( n.left, d+1, dWrap );

		//Go deeper. While there are more nodes to the right.
		if(n.right != null)
			_maxDepth(n.right, d+1, dWrap );

	}

	public static void main(String [] Args){
		Node<Integer> root =  generateTree(20);
		BTreePrinter.printNode(root);
		System.out.println( maxDepth(root) );

	}
	private static class IntWrapper{
		int val = -1;
		public IntWrapper(int v){
			this.val  = v;
		}
	}

	private static class Node<T extends Comparable<?> >{
		T data;
		Node<T> left = null;
		Node<T> right = null;

		public Node(T data){
			this.data = data;
		}
		public Node<T> addLeft( T left){
			this.left = new Node<T>(left);
			return this.left;
		}
		public Node<T> addRight( T right){
			this.right = new Node<T>(right);
			return this.right;
		}
	}

	/*
	* Pretty print method. 
	* Method shamelesly stolen from stackoverflow
	*/
	private static class BTreePrinter {

	    public static <T extends Comparable<?>> void printNode(Node<T> root) {
	        int maxLevel = BTreePrinter.maxLevel(root);

	        printNodeInternal(Collections.singletonList(root), 1, maxLevel);
	    }

    	private static <T extends Comparable<?>> void printNodeInternal(List<Node<T>> nodes, int level, int maxLevel) {
	        if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
	            return;

	        int floor = maxLevel - level;
	        int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
	        int firstSpaces = (int) Math.pow(2, (floor)) - 1;
	        int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

	        BTreePrinter.printWhitespaces(firstSpaces);

	        List<Node<T>> newNodes = new ArrayList<Node<T>>();
	        for (Node<T> node : nodes) {
	            if (node != null) {
	                System.out.print(node.data);
	                newNodes.add(node.left);
	                newNodes.add(node.right);
	            } else {
	                newNodes.add(null);
	                newNodes.add(null);
	                System.out.print(" ");
	            }

	            BTreePrinter.printWhitespaces(betweenSpaces);
	        }
	        System.out.println("");

	        for (int i = 1; i <= endgeLines; i++) {
	            for (int j = 0; j < nodes.size(); j++) {
	                BTreePrinter.printWhitespaces(firstSpaces - i);
	                if (nodes.get(j) == null) {
	                    BTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
	                    continue;
	                }

	                if (nodes.get(j).left != null)
	                    System.out.print("/");
	                else
	                    BTreePrinter.printWhitespaces(1);

	                BTreePrinter.printWhitespaces(i + i - 1);

	                if (nodes.get(j).right != null)
	                    System.out.print("\\");
	                else
	                    BTreePrinter.printWhitespaces(1);

	                BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
	            }

	            System.out.println("");
	        }

	        printNodeInternal(newNodes, level + 1, maxLevel);
	    }

	    private static void printWhitespaces(int count) {
	        for (int i = 0; i < count; i++)
	            System.out.print(" ");
	    }

	    private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
	        if (node == null)
	            return 0;

	        return Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1;
	    }

	    private static <T> boolean isAllElementsNull(List<T> list) {
	        for (Object object : list) {
	            if (object != null)
	                return false;
	        }

	        return true;
	    }

	}
}

- Optimus Prime September 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

JAVA COMPILED AND TESTED CODE

//File-1 BinarySearchTree.java
public class BinarySearchTree {

	// usually private but public because its been used
	public class Node {
		int data;
		Node left;
		Node right;

		public Node(int data) {
			this.data = data;
			this.left = null;
			this.right = null;
		}
	}

	Node root;

	public BinarySearchTree(int data) {
		root = new Node(data);
	}

	// insert routine
	public void insert(int data) {
		Node n = new Node(data);

		if (root == null) {
			root = n;
		} else {
			Node current = root;
			Node parent = null;
			while (true) {
				parent = current;
				if (data < current.data) {
					current = current.left;
					if (current == null) {
						parent.left = n;
						return;
					}
				} else {
					current = current.right;
					if (current == null) {
						parent.right = n;
						return;
					}
				}
			}
		}
	}

	// inorder traversal would print the node in the sorted order
	public void inorderTraversal(Node root) {
		if (root != null) {
			inorderTraversal(root.left);
			System.out.print(root.data + " ");
			inorderTraversal(root.right);
		}
	}
}


// File-2 BalancedTree.java
public class BalancedTree {

	public static boolean isBalanced(Node root) {
		return (maxdepth(root) - mindepth(root) <= 1);
	}

	private static int maxdepth(Node root) {
		if (root == null) {
			return 0;
		}
		return 1 + Math.max(maxdepth(root.left), maxdepth(root.right));
	}

	private static int mindepth(Node root) {
		if (root == null) {
			return 0;
		}
		return 1 + Math.min(mindepth(root.left), mindepth(root.right));
	}

	public static void main(String[] args) {

		BinarySearchTree tree = new BinarySearchTree(50);
		tree.insert(20);
		tree.insert(25);
		tree.insert(30);
		tree.insert(40);
		tree.insert(60);

		System.out.println(isBalanced(tree.root));
        System.out.println(maxdepth(tree.root));

	}

}

- Ankit October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int depthOfTree(Node root){
	if(root == null)
		return 0;
	return Math.max(depthOfTree(root.left), depthOfTree(root.right)) + 1;
}

public static int depthOfTreeIt(Node root){
	if(root == null){
		return 0;
	}

	Queue<Node> q = new Queue<Node>();
	Queue<Node> nQ = new Queue<Node>();
	q.enqueue(root);
	int level = 0;
	while(!q.isEmpty()){
		Node v = q.dequeue();
		if(v.left != null)
			nQ.enqueue(v.left);
		if(v.right != null)
			nQ.enqueue(v.right);
		if(q.isEmpty()){
			level++;
			q = nQ;
		}
	}
	return level;

}

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

// find depth of a binary tree
#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
	int data;
	struct node *left, *right;
}node;

int maxdepth(node *T)
{	
	if(T==NULL)
		return 0;
	
	else
	{
		int l_depth = maxdepth(T->left);
		int r_depth = maxdepth(T->right);
		if(l_depth > r_depth)
			return 1+l_depth;
		else
			return 1+r_depth;			
	}	
}

node *nodeInsert(int x)
{
	node *newnode = (node*)malloc(sizeof(node));

	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}


int main()
{
	node *root = nodeInsert(20);

	root->left = nodeInsert(10);
	root->right = nodeInsert(30);
	root->left->left = nodeInsert(5);
	printf("The depth of tree: %d\n", maxdepth(root));
	
	return 0;
}

- Praks November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int depth(Node root){
if(root == null){
return 0;
}
return 1 + Math.max(depth(root.left), depth(root.right));
}

- Gaurav Keswani February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int depth(Node root){
		if(root == null){
			return 0;
		} 
		return 1 + Math.max(depth(root.left), depth(root.right));
	}

- Gaurav Keswani February 14, 2016 | 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