Facebook Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
Yep that's what I thought as well: recursion. But what if recursion overhead is not acceptable for them?
@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
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;
}
}
//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;
}
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.
//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;
}
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");
}
}
}
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;
}
}
}
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));
}
}
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;
}
// 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;
}
Assuming the following structure of the binary tree
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.
- Balajiganapathi S August 13, 2014