Binary trees Interview Questions | Glassdoor

# Binary trees Interview Questions

21

interview questions shared by candidates

## Binary trees 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 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 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 18, 2012
 Given a binary tree, convert it into a doubly circular linked list. The structure of the tree was given by the interviewer and also the structure of the doubly circular linked list.2 AnswersThe elements in the DCLL were in the same order as the inorder traversal of the binary tree. So if you know how to code the inorder traversal of a tree in any language the question won't be that hard.The following blog discussed how to convert a binary search tree into a double linked list: http://codercareer.blogspot.com/2011/09/interview-question-no-1-binary-search.html

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

Jul 10, 2011
 print out binary tree's nodes in certain layout (it was in order traversal)1 Answerwrite recursive method to traverse the tree: for a given node, visit its left child, then the node, then the right child

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

Jun 13, 2009
 using recursion to traverse a binary tree 1 AnswerHere is three way to traverse the binary tree: private void InOrder(Node localRoot) { if (localRoot != null) { InOrder(localRoot.LeftChild); localRoot.Display(); InOrder(localRoot.RightChild); } } private void PostOrder(Node localRoot) { if (localRoot != null) { PostOrder(localRoot.LeftChild); PostOrder(localRoot.RightChild); localRoot.Display(); } } public void InOrderNth(Node localRoot, int n) { if (localRoot != null) { InOrderNth(localRoot.LeftChild, n); if (n == 0) localRoot.Display(); InOrderNth(localRoot.RightChild, n); } }
110 of 21 Interview Questions