# Tree Interview Questions

interview questions shared by candidates

## Tree Interview Questions

### Software Development Engineer at Amazon was asked...

Find the deepest common ancestor of two nodes in a tree structure. 13 AnswersThis interview was frustrating because it felt like the woman couldn't write code in C++. I first asked whether I could assume a standard Tree node structure (as I've built several custom structures and they all have many of the same basic components) and she was pretty much dumbstruck and told me ti write the implementation for one. So i did. Then I started walking through my solution and practically had to spell the word iterator when I said I declared one. My solution was basically to just descend in the tree toward the first value until the two values are on different sides of the current node or you fall out the bottom of the tree. I had to repeat the conditional statements character by character for the interviewer. Isn't the root node always the "deepest" common ancestor? Either the question is worded wrong, or you answered it incorrectly, but I think it's most likely that it's worded wrong. @mliu the question is correct. u r thinking wrong. depth of a tree grows towards its leaves. root is the least deep node in a tree. Show More Responses @nunnu is right here what the question wanted was the common ancestor furthest from the root. Again, I'm pretty sure (by subsequent conversations with friends) that my answer was right but that the interviewer and I just couldn't communicate struct node { int value; struct node *right; struct node *left; }mynode; mynode *closestAncestor(mynode* root, mynode* p, mynode* q) { mynode *l, *r, *tmp; if(root == NULL) { return(NULL); } if(root->left==p || root->right==p || root->left==q || root->right==q) { return(root); } else { l = closestAncestor(root->left, p, q); r = closestAncestor(root->right, p, q); if(l!=NULL && r!=NULL) { return(root); } else { tmp = (l!=NULL) ? l : r; return(tmp); } } } Smiles, my ancestors don't sit in trees. - Do yours? We have grown used to sitting under them and have great picnics... Suppose we need to find common ancestor for the nodes with values A an B. start from the root and compare value of the root node with both A and B. If A an B are both below/above the node's value then go down to the next node. Repeat until we find a node where A and B "go" to different links. This node seems to be 'common ancestor'. Traverse up the tree for both the nodes and add them to the explored list. If there is a common element in the explored list of both the nodes, that's the common ancestor. Hari, if the answer was the root your approach would have n^2*lg(n) complexity where mine had lg(n) in the worst case solution with O(h) time and memory complexity (h - height of the tree) Node * dca(const Node * a, const Node * b) { stack qa, qb; while (a) { qa.push(a); a = a->p; } while (b) { qb.push(b); b = b->p; } Node * result = NULL; while (qa.top() == qb.top()) { result = qa.top(); qa.pop(); qb.pop(); } return result; } To find the common ancestor. O(lg N) public Node GetCommonParent(Node root, int key1, int key2) { while (root != null) { int key = root.iData; if (key key1 && key > key2) root = root.LeftChild; else return root; } return null; } @Joarder: your answer is both really bad coding practice and only works for very specifically-structured trees (binary search trees based in integer keys). The approach is a good one, but you should not override a parameter being passed in and you should use Node.isLeft(Node) and Node.isRight(Node) rather than comparing keys directly. Remember that a tree can be made from a collection of any comparable object, keys are not required. Why was the first answer down voted? I think thats the best answer.. There is no better way.. And its O(log n) complexity. |

### Software Engineer at Facebook was asked...

Find the minimum depth of binary search tree 10 Answersisn't this? int mindepth(node* root) { if(root==NULL) return 0; return 1 + min(mindepth(root->left),mindepth(root->right)); } You wouldn't get an on-site interview with this answer. Your code is not optimal, although it looks short. Here is the trick: you don't have to traverse entire tree to find out the minimum. think about this example. L side of the root node has only one item, so the deep is 1, R side of the root has one million items. Why do you have to traverse through all one million nodes, if you can get the min from the L side right away? It can be solved using the previous recursive code and also can be solved using Breadth First Traversal, by starting the traversal from the root of the tree, and when reach a leaf then this is the min depth return the number of steps from the root to this leaf Show More Responses public int minDepth(Node root) { Map depthMap = new HashMap(); depthMap.put(root, 0); List toVisit = new ArrayList(); toVisit.add(root); while(!toVisit.isEmpty()) { Node curr = toVisit.remove(0); if(curr.getLeft() == null && curr.getRight() == null) { // first leaf node is the minimum depth return depthMap.get(curr); } else { if(curr.getLeft() != null) { depthMap.put(curr.getLeft, depthMap.get(curr) + 1); toVisit.add(curr.getLeft()); } if(curr.getRight() != null) { depthMap.put(curr.getRight(), depthMap.get(curr) + 1); toVisit.add(curr.getRigth()); } } } return -1; // not good } use a BFS. And use int used and int inquery. And the sum = used+inquery to identify if current node's level. It is binary tree so it has the property of the 2^(n+1)-1! node for full tree. And I think the Standard BFS is to use a query to keep everything. One problem is that ur query will grow big very fast! Someone said you need to pass 3 questions to be qualified to on-site... Use BFS to iterate the tree, keep track of the "level" you're currently at. When a childless node shows up, return the level number. Code: public static int MinDepth(Node root) { if (root==null) { return 0; } Queue queue = new LinkedList(); queue.add(root); queue.add(new Sentinel()); int depth = 1; while(!queue.isEmpty()){ Node current = queue.poll(); if (!(current instanceof Sentinel)) { if (current.left==null && current.right==null) { break; } else { if (current.left!=null) queue.add(current.left); if (current.right!=null) queue.add(current.right); } } else { depth++; if (!queue.isEmpty()) { queue.add(new Sentinel()); } } } return depth; } void mindepth(node* cur, int curdepth, int& best) { if(curdepth >= best) return; if(cur == null) { best = curdepth; return; } mindepth(cur->left, curdepth + 1, best); mindepth(cur->right, curdepth +1, best); } best = inf; mindepth(root, 0, best); public class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } Queue<div>q = new LinkedList<div>(); q.add(root); int enqueuedNum = 1; int visitedNum = 0; int lastLevelNum = 1; // initialized to be 1, whichever child tree node is null, then finish // the operation and return the current minDepth int minDepth = 1; while (true) { TreeNode n = q.poll(); visitedNum++; if (n.left != null) { q.add(n.left); enqueuedNum++; } if (n.right != null) { q.add(n.right); enqueuedNum++; } if (n.left == null || n.right == null) { return minDepth; } if (lastLevelNum == visitedNum) { lastLevelNum = enqueuedNum; minDepth++; } } } }</div></div> |

Write a function that takes 2 arguments: a binary tree and an integer n, it should return the n-th element in the inorder traversal of the binary tree. 7 AnswersCorrect answer should be something like this: int FindNthElement(Node *node, int &n) { if (node->Left && n > 0) { k = FindNthElement(node->left, n); if (n == 0) return k; } if (n == 0) return node->value; else if (n > 0 && node->right) { k = FindNthElement(node->right, n); if (n == 0) return k; else return -1; } } int findNthElementByInorder(Node *node, int &n) { if (node == null) return -1; findNthElementByInorder(node->left, n); if (n == 0) return node-> value; else n--; findNthElementByInorder(node->right, n); } Seems it should be something like this, get the to bottom and start counting up from there. int start(Node *node, int &n) { int element = 0; if (node == null) return -1; return findElementIndex(node, element, n); } int findElementIndex(Node *node, int ¤tNumber, int findNumber) { if(node->left != null ) { int result = findElementIndex(node->left, currentNumber, findNumber); if(result != -1) return result; } if(node->right != null ) { int result = findElementIndex(node->right, currentNumber, findNumber); if(result != -1) return result; } currentNumber++; if(currentNumber == findNumber) return node->value; else return -1; } Show More Responses //Assumption is that the node values are not negative. //If the tree has less than n nodes, -1 will be returned. int findNthElementByInorder(Node *node, int &n) { if ((node != null) && (n > 0)) { findNthElemetnByInorder(node>left, n); n--; //Count the current node findNthElemetnByInorder(node>right, n); return node->value; } else return -1; } def nth_inorder_node(treeNode, counter) # Check left node if treeNode.left rv = nth_inorder_node(treeNode.left, counter) return rv if rv end # Check current node counter.value -= 1 puts "counter: #{counter.value} \t node: #{treeNode.data}".green return treeNode.data if counter.value == 0 # Check right node if treeNode.right rv = nth_inorder_node(treeNode.right, counter) return rv if rv end return nil end int nthelement(Node node, int n){ int ret; if( node.left != null) { ret = nthelement(node.left, n); if(ret != -1) return ret; } n --; if(n ==0) return node.data; if(node.right != null) { ret = nthelement(node.right, n); if(ret!= -1) return ret; } return -1; } int [] results; int count = 0; int returnNthElement(Node rootNode, int element) { fillArray(rootNode); return results[element]; } void fillArray(Node node) { if (node == null) { return null; } if (node.left == null && node.right == null) { count++; results[count] = node; return; } fillArray(node.left); count ++; results[count] = node; fillArray(node.right); } |

### Software Engineer at Google was asked...

Define binary search tree. Develop a procedure to verify a binary search tree. 6 AnswersNot very difficult. Asked for answer in code. Interviewer took notes for each line I wrote. Was interested in each statement I made about the algorithm, esp. why I took each approach. How do you verify a binary search tree? Will you get all the values from binary search tree and check if they are in order? can someone explain? @Bala Recursively: Check node.left node.value. Also, that all subvalues of node.left node.value. Make sure you do checking for edge cases (ie. leaf nodes, etc). Show More Responses recursive solution is a good option i guess.. its definitely easy to code. However i think we can have it done more efficiently if we just perform a BFS on the given tree. and every time just check tht the left child is smaller and right chiled is greater than or equal to the current node. If we successfully search the entire tree then it is a proper BST otherwise its not. public static boolean checkTree(BSTNode node, Integer leftLimit, Integer rightLimit) { if(node == null) return true; if(leftLimit != null && leftLimit > node.info) { return false; } if(rightLimit != null && rightLimit < node.info) { return false; } return checkTree(node.left,leftLimit,node.info) && checkTree(node.right,node.info,rightLimit); } bool IsValidBST(Node root, int min, int max) { if(root == null) return true; if (root.iData > min && root.iData < max && IsValidBST(root.LeftChild, min, root.iData) && IsValidBST(root.RightChild, root.iData, max)) return true; else return false; } |

First explain what a tree, then binary tree, then a binary search tree is. Now implement a function that verifies whether a binary tree is a valid binary search tree. 5 AnswersSadly I ran out of time for this question. But I e-mailed the response after my time was up. First create a small implementation of a binary tree, I did it in java with the standard implementation Nodes with left and right children as data points. Check whether the left child and right child have valid values, which is to say make sure all children on the right of a node have values greater than parents that they came from. The key thing that I missed during the interview was the fact that if you traverse once to the right, then once to the left, you have to make sure the value is between the max and min that you've encountered up to that point. int validate_BST(struct tnode *tree){ int ret1, ret2; if (tree == NULL) return 1; else { if (tree->left != NULL){ if (tree->data > tree-left->data){ ret1 = validate_BSR(tree->left); } else return 0; } if (tree->right != NULL) { if (tree->data right->data){ ret2 = vaidate_BSD(tree->right); } else return 0; } return (ret1 == 1 && ret2 == 1)? 1: 0; } return 0; } To find whether a binary tree is valid Binary search tree, do inorder traversal and check if the nodes are sorted. Show More Responses private boolean isBST(){ return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean isBST(Node node, int min, int max){ if(node == null) return true; if(node.data max) return false; else return (isBST(node.left, min, node.data) && isBST(node.right, node.data+1, max)); } In order to verify the Binary Search Tree, Read the nodes in Inorder mode. Also at every step check if the current node value is less than the one previously found then exit the traversal as the items are not sorted. |

Write an algorithm that does an in-order traversal of a tree recursively. Now, write the same algorithm iteratively. 4 AnswersHint: You'll want to use a stack in the iterative version. Haha, I got that same question on my interview. It made me sweat, because I knew I was supposed to use a stack, but I had never done it before. It was fun working it out on my own. public void inOrder(Node* root) { if(root == NULL) return; inOrder(root->left); cout element; inOrder(root->right); } Show More Responses // recursive void InorderTraversal( Node *root) { if ( root== NULL) return ; // status 2 InorderTraversal( root->left ); // status 1 Print (root); InorderTraversal(root->right); // status 0 } // NON-Recursive Version for Pre/In/Post-Order the idea behind this method is to employ a stack to emulate the recursion void NonRecTraversal( Node *root ) { if ( root == NULL ) return ; stack stk; bool flag = 2;// the key: keep track of the status of the top element stk.push(root); while( !stk.empty()) { if ( flag == 2 ) { /* Print (node) ; this is preorder */ if ( stk.top()->left != NULL ) stk.push(stk.top()->left ); else flag = 1; } else if ( flag == 1) { /* Print (node) ; this is inorder */ if ( stk.top()->right != NULL) { stk.push(stk.top()->right); flag = 2; } else flag = 0; } else { /* Print (node) ; this is postorder */ Node *temp = stk.top(); Stk.pop(); If ( !stk.empty() && stk.top()->left == temp ) Flag = 1; // come back from left child Else Flag = 0; // come back from right child } } } |

In a BST write a program to find 2 nodes x and y such that X+y=k 4 AnswersI think we need to do traversals and check for every node. For a given x traverse nodes upto x + y <= k. This problem requires the use of a map aka dictionary aka hashtable. Visit a node If the node data isn't in the map; add the data to the map. Solve for what the other number should be; check if it's in the map. if it is you're done... otherwise keep searching. Show More Responses You can solve the problem in O(n) time. First you find the smallest number in the tree then you find the highest number (worst-case linear time, logarithmic time if the BST is balanced). If their sum is larger than K, you find the largest number in the tree that is lower than y (you can do it in amortized constant time) If their sum is lower than K, you find the smallest number in the tree that is higher than x (amortized constant time). And you continue this algorithm until you reach the correct X and Y :) |

### Software Engineer at Symantec was asked...

find lowest common ancestor of 2 nodes in a binary tree 3 AnswersI tried a complicated recursive methods and got stuck. If there is no restriction, we actually could use an hash map to store tree nodes while tracing up the parent nodes of the given nodes. if a common node is found to be parent of the given 2 nodes then print it out Node lowestCommonAncestor(Node root, Node a, Node b) { if (root.contains(a) && root.contains(b)) { if (root.left != null && root.left.contains(a) && root.left.contains(b)) return lowestCommonAncestor(root.left, a, b); else if (root.right != null && root.right.contains(a) && root.right.contains(b)) return lowestCommonAncestor(root.right, a, b); else return root; } else return null; } boolean contains(Node root, Node x) { if (root == null || x == null) return false; // not needed. Defensive coding if (root == x) return true; if (root.left != null and root.left.contains(x)) return true; if (root.right != null and root.right.contains(x)) return true; return false; } int lowestCommonAncestor(Node node, int value1, int value2){ if(node == null) return -1; if(value1 > node.data && value2 > node.data) return lowestCommonAncestor(node.right, value1, value2); else if(value1 < node.data && value2 < node.data) return lowestCommonAncestor(node.left, value1, value2); else return node.data; } |

### Software Engineer at PEAK6 Investments was asked...

Find the height of a binary tree 3 AnswersClass Node { int data; Node left; Node right; } public static int heightOfTree(Node node) { if(node!=null) { return (heightOfTree(node.left)+1+heightOfTree(node.right)); } } The above post gives too big of an answer except in trees that are technically Linked Lists. Replace the return line with the following to *actually* get the height of a tree: return 1 + max(heightOfTree(node.left), heightOfTree(node.right)); Also, the above function could possibly terminate without returning anything. Add an else condition that returns 0 as the base case. /** Returns the max root-to-leaf depth of the tree. Uses a recursive helper that recurs down to find the max depth. */ public int maxDepth() { return(maxDepth(root)); } private int maxDepth(Node node) { if (node==null) { return(0); } else { int lDepth = maxDepth(node.left); int rDepth = maxDepth(node.right); // use the larger + 1 return(Math.max(lDepth, rDepth) + 1); } } |

### Software Development Engineer at Amazon was asked...

Serialize (flatten) and de-serialize a binary tree. First describe the approach, then write the code. 3 AnswersI know that some people didn't get to the de-serialization code...so it might be a bit long. The question itself is pretty basic so the objective should be to provide a clear explanation and code. Interviewer seemed happy that I didn't jump straight to the solution, but instead inquired about any system restrictions, requirements etc. http://www.leetcode.com/2010/09/serializationdeserialization-of-binary.html For BST http://www.leetcode.com/2010/09/saving-binary-search-tree-to-file.html |

**1**–

**10**of

**33**Interview Questions