Trees Interview Questions and Answers

Trees are well-known as a non-linear data structure. They don’t store data in a linear way. They organize datahierarchically. A tree is a collection of entities called nodes. Nodes are connected by edges. Each node contains a value or data or key, and it may or may not have a child node. The first node of the tree is called the root. Leaves are the last nodes on a tree. They are nodes without children.

A normal tree has no restrictions on the number of children each node can have. A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. There are three different types of binary trees: Full binary tree: Every node other than leaf nodes has 2 child nodes. Complete binary tree: All levels are filled except possibly the last one, and all nodes are filled in as far left as possible. Perfect binary tree: All nodes have two children and all leaves are at the same level.

For small data: insert: RB tree & avl tree has constant number of max rotation but RB tree will be faster because on average RB tree use less rotation. lookup: AVL tree is faster, because AVL tree has less depth. delete: RB tree has constant number of max rotation but AVL tree can have

O(
log n) times of rotation as

worst. and on average RB tree also has less number of rotation thus RB tree is faster. For large data: insert: AVL tree is faster. because you need to lookup for a particular node before insertion. as you have more data the time difference on looking up the particular node grows proportional to

O(
log n) . but AVL tree

& RB tree still only need constant number of rotation at the worst case. Thus the bottle neck will become the time you lookup for that particular node. lookup: AVL tree is faster. (same as in small data case) delete: AVL tree is faster on average, but in worst case RB tree is faster. because you also need to lookup for a very deep node to swap before removal (similar to the reason of insertion). on average both trees has constant number of rotation. but RB tree has a constant upper bound for rotation. In overall AVL trees maintain a more rigid balance than red-black trees. The path from the root to the deepest leaf in an AVL tree is at most ~1.44 lg(n+2) , while in red black trees it's at most ~2 lg (n+1) . As a result, lookup in an AVL tree is typically faster, but this comes at the cost of slower insertion and deletion due to more rotation operations. So use an AVL tree if you expect the number of lookups to dominate the number of updates to the tree.

A red-black tree is a binary search tree in which each node has a color (red or black) associated with it (in addition to its key and left and right children). This can be saved in memory as a single bit (e.g. 'red' = 1, 'black' = 0). the following 3 properties hold: (root property) The root of the red-black tree is black (red property) The children of a red node are black. (black property) For each node with at least one null child, the number of black nodes on the path from the root to the null child is the same. This is sometimes known as the black-depth. The height of the red-black tree is at most 2*log(n + 1)

Red-black trees maintain a slightly looser height invariant than AVL trees. Because the height of the red-black tree is slightly larger, lookup will be slower in a red-black tree. However, the looser height invariant makes insertion and deletion faster. Also, red-black trees are popular due to the relative ease of implementation.

Inserting a key into a non-empty tree has three steps. In the first step, the BST insert operation is performed. The BST insert operation is O (height of tree) which is O(log n) because a red-black tree is balanced. The second step is to color the new node red. This step is O(1) since it just requires setting the value of one node's color field. In the third step, we restore any violated red-black properties. Restructuring is O(1) since it involves changing at most five pointers to tree nodes. Once a restructuring is done, the insert algorithm is done, so at most 1 restructuring is done in step 3. So, in the worst-case, the restructuring that is done during insert is O(1) . Changing the colors of nodes during recoloring is O(1) . However, we might then need to handle a double-red situation further up the path from the added node to the root. In the worst-case, we end up fixing a double-red situation along the entire path from the added node to the root. So, in the worst-case, the recoloring that is done during insert is O(log N) ( = time for one recoloring * max number of recolorings done = O(1) * O(log N) ). Thus, the third step (restoration of red-black properties) is O(log N) and the total time for insert is O(log N) .

Complexity Analysis: Time Complexity: O(log n) Space Complexity: O(log n)

To ensure that its color scheme and properties don’t get thrown off, red-black trees employ a key operation known as rotation. Rotation is a binary operation, between a parent node and one of its children, that swaps nodes and modifys their pointers while preserving the inorder traversal of the tree (so that elements are still sorted). There are two types of rotations: left rotation and right rotation. Left rotation swaps the parent node with its right child, while Right rotation swaps the parent node with its left child.

B-tree is a self-balancing tree data structure that maintains sorted data. B-tree stores data such that each node contains keys in ascending order. Unlike a binary tree, each node in a B-Tree can have more than 2 children. Each node can have up to m children, where m is called the tree’s “order”. Unlike self-balancing binary search trees, it is optimized for systems that read and write large blocks of data. It is most commonly used in database and file systems. By maximizing the number of keys within each internal node, the height of the tree decreases and the number of expensive node accesses is reduced. In addition, rebalancing of the tree occurs less often. B-trees may waste some space, since nodes are not entirely full.

Consider an apartment complex/condo community that you are visiting, with 1000 apartments/Condos spread among several buildings and a gate in the middle. As you drive in the first board you meet says 1-500 501-1000 <- -> The Apartment number you want to visit is 807, so take right. Next you see buildings each with numbers such as 501-550, 551-600 etc. Again you pick the building which says 801-850. Next you pick the floor which says 801- 810 and finally apartment 807 itself. Now imagine not having the boards with numbers on them. you would have to visit every single apartment in the community to decide if apartment 807 is present there. Also, if the apartment community was not allowed to be split that way, It would be one huge building with 1000 individual apartments in it. A B Tree and a B+Tree are data structures used within a computer to achieve results similar to what is described in the example above

if you want to compare AVL tree with simple binary search tree (BST) without balancing, then AVL: will consume more memory (each node has to remember its balance factor) and each operation can be slower (because you need to maintain the balance factor and sometimes perform rotations). BST without balancing has a very bad (linear) worst case. But if you know that this worst case won't happen to you, or if you're okay if the operation is slow in rare cases, BST without balancing might be better than AVL.

When inserting values into the AVL tree, the tree may become unbalanced, we can check if it is balanced or not by using the balance factor to make sure the height of the sub-tree doesn’t differ by more than 1. The balance factor of a node (N) in a binary tree is defined as the height difference:

BalanceFactor(N) = height(left_sutree(N)) − height(right_sutree(N))
// BalanceFactor(N) belongs to the
set {-1,0,1}
If the balance factor

of a tree doesn’t equal -1,0, or 1 then our tree is unbalanced: BalanceFactor = height(left_sutree) − height(right_sutree)

// BalanceFactor not in {-1,0,1} => UNBALANCED
and we need to perform certain operations (called rotations) to balance the tree. Specifically we need to do one

or more of 4 tree rotations: Single Rotations: Left Left Rotation Right-Right Rotation, Double Rotation: Left Right Rotation or Double Left, Right Left Rotation or Double Right. Now, we say that a sub-tree is: left-heavy if the balance factor is greater than zero (> 0) right-heavy if the balance factor is lesser than zero (< 0)

How we determine which rotation to use follows a few basic rules. See psuedo code:

IF tree is left heavy {
  IF tree 's left subtree is right heavy {
    Perform Double Right rotation
    /*
    c b
    / / \
    a == 2R ==> a c
    \
    b
    */
  }
ELSE { // Left Left case
  Perform Single Right rotation
  /*
  c b
  / / \
  b == 1R ==> a c
  /
  a
  */
}
}
IF tree is right heavy {
  IF tree 's right subtree is left heavy {
    Perform Double Left rotation
    /*
    a b
    \ / \
    c == 2L ==> a c
    /
    b
    */
  }
ELSE { // Right Right Case
  Perform Single Left rotation
  /*
  a b
  \ / \
  b == 1L ==> a c
  \
  c
  */
}
}

In general it may or may not depending on the particular graph. A depth-first search uses a stack, which contains nodes from root to the node being searched. So at most the radius of the graph. A breadth-first search uses a queue, which contains nodes at the front of the search. So at most all nodes at distance d. In general graph all you can say is that it's at most all nodes in the tree in either case. But if you have a balanced

(or mostly so)
k-ary tree, it's depth, i.e. radius, will be only O(log n) , while the lowest layer will contain O(n)
nodes ( n/2 for binary tree and even more for higher degrees). For example, in a (balanced) tree with 1023

nodes the DFS has to keep track of 10 nodes, while the BFS has to keep track of 512 nodes. So depth-first search will only use O(log n) memory and breadth-first search will use O(n) . For balanced k-ary trees; for other cases different results are possible (but for most common graphs diameter will still be significantly less than circumference). Note that BFS doesn't always use more memory: More specifically, BFS uses O(branchingFactor^maxDepth) or O(maxWidth) memory, where-as DFS only uses

O(maxDepth) .
If maxWidth < maxDepth , BFS should use less memory (assuming you use similar representations for both), but

this is rarely true.

First think about: BSF searches for siblings first. DFS obviously searches for children first. So relationship type searches across fields would probably lend itself to BFS, where hierarchical (trees, folders, ranks, etc) would be more suited as a DFS. BFS is going to use more memory depending on the branching factor ( O(branchingFactor^maxDepth) ), however, BFS is a complete algorithm meaning if you are using it to search for something in the lowest depth possible, BFS will give you the optimal solution. BFS space complexity is O(b^d) , the branching factor raised to the

depth (can be a lot of memory).

DFS on the other hand, is much better about space however it may find a suboptimal solution. Meaning, if you are just searching for a path from one vertex to another, you may find the suboptimal solution (and stop there) before you find the real shortest path. DFS space complexity is O(|V|) ... meaning that the most memory it can take up is the longest possible path (the radius of the graph). The time complexity for both is O(b^d) meaning it is based on the branching factor and the depth searched. BFS and DFS have the same worst case that is searching the entire tree. In terms of implementation, BFS is usually implemented with Queue , while DFS uses a Stack . Some other considerations you may apply: If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster.

If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

The major difference between a binary heap and a red-black tree is the performance on certain operations: Heap Pros It makes an ideal priority queue, since the min/max element (depending on your implementation) is always O(1) access time, so no need to search for it. It's also very fast for insertion of new values - O(1) on average, O(log n) worst case. Heap Cons Slow searches O(n) for random elements. RB Tree Pros Better searching O(log n) and good insertion O(log n) performance. RB Tree Cons Slower min/max searches. More overhead in general.

Both the AVL tree and the B-tree are similar in that they are data structures that, through their requirements, cause the height of their respective trees to be minimized. This "shortness" allows searching to be performed inO( log n) time, because the largest possible number of reads corresponds to the height of the tree. But: An AVL tree is a self-balancing binary search tree. AVL trees are intended for in-memory use, where random access is relatively cheap. AVL trees are not designed to hold massive collections of data, as they use dynamic memory allocation and pointers to the next block of memory. A B-tree is a balanced tree, but it is not a binary tree )rather it's multi-way tree (N-ary tree)). B-Trees are better suited for disk-backed storage. A B-tree holds many children at one node and many pointers to children node. This way, during a disk read (which can take around 10 ms to read a single disk block), the maximum amount of relevant node data is returned, as well as pointers to "leaf node" disk blocks. This allows retrieval time of data to be amortized to log(n) time, making the B-tree especially useful for database and large dataset retrieval implementations.

Red-black trees are more general purpose. Both red-black trees and AVL trees are the most commonly used balanced binary search trees and they support insertion, deletion and look-up in guaranteed O(log n) time. However, there are following points of comparison between the two: AVL trees are more rigidly balanced and hence provide faster look-ups. Thus for a look-up intensive task use an AVL tree. For an insert intensive tasks, use a Red-Black tree. RB-Trees guarantee O(1) rotations per insert operation AVL trees store the balance factor at each node. This takes O(n) extra space. However, if we know that the keys that will be inserted in the tree will always be greater than zero, we can use the sign bit of the keys to store the colour information of a red-black tree. Thus, in such cases red-black tree takes no extra space. RB Trees do relatively well on: add, remove, and look-up AVL trees have: faster look-ups (AVL tree is, usually, has better balance ~1.44 log(N) than RB-tree 2 log(N) ) at the cost of slower add/remove.

Both the AVL tree and the B-tree are similar in that they are data structures that, through their requirements, cause the height of their respective trees to be minimized. This "shortness" allows searching to be performed inO( log n) time, because the largest possible number of reads corresponds to the height of the tree. But: An AVL tree is a self-balancing binary search tree. AVL trees are intended for in-memory use, where random access is relatively cheap. AVL trees are not designed to hold massive collections of data, as they use dynamic memory allocation and pointers to the next block of memory. A B-tree is a balanced tree, but it is not a binary tree )rather it's multi-way tree (N-ary tree)). B-Trees are better suited for disk-backed storage. A B-tree holds many children at one node and many pointers to children node. This way, during a disk read (which can take around 10 ms to read a single disk block), the maximum amount of relevant node data is returned, as well as pointers to "leaf node" disk blocks. This allows retrieval time of data to be amortized to log(n) time, making the B-tree especially useful for database and large dataset retrieval implementations.

The main reason for the existence of B-Trees is to better utilize the behaviour of devices that read and write large chunks of data. Two properties are important to make the B-Tree better than binary trees when data has to be stored on disk:

Access to disk is really slow (compared to memory or caches, random access to data on disk is orders of magnitude slower); and Every single read causes a whole sector to be loaded from the drive - assuming a sector size of 4K, this means 1000 integers, or tens of some larger objects you're storing. Hence, we can use the pros of the second fact, while also minimizing the cons - i.e. number of disk accesses. So, instead of just storing a single number in every node that tells us if we should continue to the left or to the right, we can create a bigger index that tells us if we should continue to the first 1/100, to the second or to the 99-th (imagine books in a library sorted by their first letter, then by the second, and so on). As long as all this data fits on a single sector, it will be loaded anyway, so we might as well use it completely. This results in roughly logb N lookups, where N is the number of records. This number, while asymptotically the same as log N, is actually a few times smaller with large enough N and b - and since we're talking about storing data to disk for use in databases, etc., the amount of data is usually large enough to justify this.

The image below helps show the differences between B+ trees and B trees. Advantages of B+ trees: Because B+ trees don't have data associated with interior nodes, more keys can fit on a page of memory. Therefore, it will require fewer cache misses in order to access data that is on a leaf node. The leaf nodes of B+ trees are linked, so doing a full scan of all objects in a tree requires just one linear pass through all the leaf nodes. A B tree, on the other hand, would require a traversal of every level in the tree. This full-tree traversal will likely involve more cache misses than the linear traversal of B+ leaves. Advantage of B trees: Because B trees contain data with each key, frequently accessed nodes can lie closer to the root, and therefore can be accessed more quickly.

Think about B-Tree as a type of dictionary, no more and no less. It can be used to implement a set (e.g. see the interface for java.util.Set ), but is most commonly used to implement a map (ditto for java.util.Map ). If you think about a linguistic dictionary, it's ordered by "word", and associated with each word is a definition. You look up a word, and get a definition. The main advantage of B-trees over other kinds of search tree is that it is particularly efficient when represented on disk. B-trees are page-structured (meaning they can be implemented on top of fixed-size disk pages; this also avoids fragmentation), and have a wide ply, which minimises the number of disk accesses needed to perform a query. A typical use of B-Trees is to implement DB indexes. A database index typically maps a key to a set of database records. In a typical organisation, there is one data structure in which records are stored, and multiple indexes which map keys to record identifiers. To find records, you query the index, which gives you a collection of record identifiers. Then you can use those record identifiers to find the records in the store. A typical use in a modern filesystem is to implement directories ("folders" if you're more used to GUIs). A directory is, logically, a map from names (file names or directory names) to filesystem objects. A filesystem object may be a file, or another directory, or what have you.

The depth of a node is the length of the path to its root The height of a node is the number of edges on the longest path from the node to a leaf The height of a tree is the length of the longest path to a leaf root node inner node leaf node

3 h=3
d=0
6 h=2
d=1
7 h=0
d=25 h=1
d=2
4 h=0
d=3
2 h=1
d=1
1 h=0
d=2

That is a basic (generic) tree structure that can be used for String or any other object: Implementation: Java

public class Tree<T> {
  private Node<T> root;
  public Tree(T rootData) {
    root = new Node<T>();

    root.data = rootData;
    root.children = new ArrayList<Node<T>>();
  }
public static class Node<T> {
  private T data;
  private Node<T> parent;
  private List<Node<T>> children;
}
}
PY
Generic Tree:
class Tree(object):
"Generic tree node."
def __init__(self, name='root', children=None):
self.name = name
self.children = []
if children is not None:
for child in children:
self.add_child(child)
def __repr__(self):

return self.name def add_child(self, node):

assert isinstance(node, Tree)
self.children.append(node)
# *
# /|\
# 1 2 +
# / \
# 3 4
t = Tree('*', [Tree('1'),
Tree('2'),
Tree('+', [Tree('3'),
Tree('4')])])
Binary tree:
class Tree:
def __init__(self):
self.left = None
self.right = None
self.data = None

Graph: Consists of a set of vertices (or nodes) and a set of edges connecting some or all of them Any edge can connect any two vertices that aren't already connected by an identical edge (in the same direction, in the case of a directed graph) Doesn't have to be connected (the edges don't have to connect all vertices together): a single graph can consist of a few disconnected sets of vertices

Could be directed or undirected (which would apply to all edges in the graph) Tree: A type of graph (fit with in the category of Directed Acyclic Graphs (or a DAG)) Vertices are more commonly called "nodes" Edges are directed and represent an "is child of" (or "is parent of") relationship Each node (except the root node) has exactly one parent (and zero or more children) Has exactly one "root" node (if the tree has at least one node), which is a node without a parent Has to be connected Is acyclic, meaning it has no cycles: "a cycle is a path [AKA sequence] of edges and vertices wherein a vertex is reachable from itself" Trees aren't a recursive data structure

Binary search tree is a data structure that quickly allows to maintain a sorted list of numbers. It is called a binary tree because each tree node has maximum of two children. It is called a search tree because it can be used to search for the presence of a number in O(log n) time. The properties that separates a binary search tree from a regular binary tree are: All nodes of left subtree are less than root node All nodes of right subtree are more than root node Both subtrees of each node are also BSTs i.e. they have the above two properties

Tree Traversal algorithms can be classified broadly in two categories:

Depth-First Search (DFS) Algorithms
Breadth-First Search (BFS) Algorithms
Depth-First Search (DFS) Algorithms have three variants:
1. Preorder Traversal (current-left-right)— Visit the current node before visiting any nodes inside left or right
subtrees.
2. Inorder Traversal (left-current-right)— Visit the current node after visiting all nodes inside left subtree but

before visiting any node within the right subtree. 3. Postorder Traversal (left-right-current) — Visit the current node after visiting all the nodes of left and right subtrees. Breadth-First Search (BFS) Algorithm has one variant:

1. Level Order Traversal — Visit nodes level-by-level and left-to-right fashion at the same level.

Depth-first searches are often used in simulations of games (and game-like situations in the real world). In a typical game you can choose one of several possible actions. Only some paths in a game tree lead to your win. Some lead to a win by your opponent, when you reach such an ending, you must back up, or backtrack, to a previous node and try a different path. In this way you explore the tree until you find a path with a successful conclusion. Another example, given a family tree if one were looking for someone on the tree who’s still alive, then it would be safe to assume that person would be on the bottom of the tree. This means that a BFS would take a very long time to reach that last level. A DFS, however, would find the goal faster. The breadth-first search has an interesting property: It first finds all the vertices that are one edge away from the starting point, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting vertex to a given vertex. Breadth-first search can be used for finding the neighbour nodes in peer to peer networks like BitTorrent, GPS systems to find nearby locations, social networking sites to find people in the specified distance.

AVL trees are height balancing binary search tree. It is named after Adelson-Velsky and Landis, the inventors of the AVL tree. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor. This allows us to search for an element in the AVL tree in O(log n) , where n is the number of elements in the tree. The balance factor of a node (N) in a binary tree is defined as the height difference:

BalanceFactor(N) = height(left_sutree(N)) − height(right_sutree(N))
// BalanceFactor(N) belongs to the
set {-1,0,1}

If the balance factor doesn’t equal -1,0, or 1 then our tree is unbalanced, and we need to perform certain operations (called rotations) to balance the tree. Specifically we need to do one or more of 4 tree rotations: Left Rotation, Right Rotation, Left Right Rotation, Right Left Rotation.

A tree is said to be balanced only when all three conditions satisfy: The left and right subtrees height differ by at most one The left subtree is balanced

The right subtree is balanced Height-balancing requirement: A node in a tree is height-balanced if the heights of its subtrees differ by no more than 1. A tree is height-balanced if all of its nodes are height-balanced. In a balanced BST, the height of the tree is log n where n is the number of elements in the tree. In the worst case and in an unbalanced BST, the height of the tree can be upto n which makes it same as a linked list. In the worst case each of the operations (lookup, insertion and deletion) takes time O(n) that shall be avoided. Balanced BST maintains h = O(log n) so all operations run in O(log n) time.

Advantages of BST: If we implement a balanced binary search tree, we can always keep the cost of insert() , delete() ,

lookup() to O(log n)
BST is much faster than an array at search, insert, and delete ( O(log n) vs O(n) )

Code is simple relative to other data structures Disadvantages of BST: BST is slightly slower than an array at access ( O(log n) vs O(1) ) A binary search tree can get out of balance ( imbalanced) or become degenerated We should always implement a balanced binary search tree (using some

self-balancing mechanism) - AVL

tree, Red-Black tree, Splay tree. Otherwise the cost of operations may not be logarithmic and degenerate into a linear search on an array.

If we implement a balanced binary search tree, we can always keep the cost of insert() , delete() , lookup() to O(log n) where n is the number of nodes in the tree - so the benefit really is that lookups can be done in logarithmic time which matters a lot when n is large. This is much better than the

linear time O(n)
required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash
tables.

Binary tree: Tree where each node has up to two leaves 1 /
2 3 Binary Search Tree (BST): Used for searching. A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the parent. 2 /
1 3

Diameter of tree is defined as a longest path or route between any two nodes in a tree. The path may or may not for through the root.

Depth and height are properties of a node: The depth of a node is the number of edges from the node to the tree's root node. A root node will have a depth of 0. The height of a node is the number of edges on the longest path from the node to a leaf. A leaf node will have a height of 0.

Properties of a tree: The height of a tree would be the height of its root node, or equivalently, the depth of its deepest node. The diameter (or width) of a tree is the number of nodes on the longest path between any two leaf nodes. The tree below has a diameter of 6 nodes.