Tree Interview Questions | Glassdoor

# Tree Interview Questions

33

interview questions shared by candidates

## Tree Interview Questions

Sort: RelevancePopular Date

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

Oct 15, 2009

Dec 9, 2010
(); 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++; } } } }

Aug 5, 2012
 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 &currentNumber, 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 endint 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); }

Jan 24, 2010
 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 Responsesrecursive 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; }

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

Jan 27, 2012
 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 Responsesprivate 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.

### Software Development Engineer In Test (SDET) at Microsoft was asked...

Jun 18, 2011
 In a BST write a program to find 2 nodes x and y such that X+y=k4 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 ResponsesYou 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...

Jul 10, 2011
 find lowest common ancestor of 2 nodes in a binary tree3 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 outNode 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 Development Engineer Intern at Microsoft was asked...

Mar 18, 2009
 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 } } }

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

May 15, 2011
 Find the height of a binary tree3 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...

Jun 25, 2012
 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.htmlFor BST http://www.leetcode.com/2010/09/saving-binary-search-tree-to-file.html
110 of 33 Interview Questions