[Data Structures] Trees (BT, BST)

A Tree is a recursive explanation. A tree is a data structure composed of nodes.

• Each tree has a root node. (Actually, this isn't strictly necessary in graph theory, but it's usually how we use trees in programming, and especially programming interviews)
• The root node has zero or more child nodes
• Each child node has zero or more child nodes, and so on. 

 

The tree cannot contain cycles. The nodes may or may not be in a particular order, they could have any data type as values, and they may or may not have links back to their parent nodes.

 

A very simple class definition for Node is:

class Node {
    public String name;
    public Node[] children;
}

You might also have a Tree class to wrap this node. For interview questions, we typically do not use a Tree class. You can if you feel it makes your code simpler or better, but it rarely does.

public class Tree {    
    public Node root;
}

 

Tree and Graph questions are rife with ambiguous details and incorrect assumptions. Be sure to watch out for the following issues and seek clarification when necessary.

 

 

Trees vs Binary Tree

A binary tree is a tree where each node has up to two children. Not all trees are binary trees. For example, this tree is not a binary tree. You could call it a ternary tree.

There are occasions when you might have a tree that is not a binary tree. For example, suppose you were using a tree to represent many phone numbers. In this case, you might use a 10-ary tree, with each node having up to 10 children (one for each digit)

 

A node is called a "leaf"node if it has no children.

 

Binary Tree vs. Binary Search Tree

A binary search tree is a binary tree in which every node fits a specific ordering property:

 

all left descendants >= n < all right descendants.

 

This must be true for each node n.

 

Node that this inequality must be tree for all of a node's descendants, not just its immediate children. The following tree on the left below is a binary search tree. The tree on the right is not.

For the interview, you should ask if the interviewer means BST or just a BT.

 

Balanced vs Unbalanced

While many trees are balanced, not all are. Ask your interviewer for clarification here. Note that balancing a tree does not mean the left and right subtrees are exactly the same size (like you see under "perfect binary trees" in the following diagram)

 

"Balanced" tree means something more like "not terribly imbalanced" It's balanced enough to ensure O(log n) times for insert and find, but it's not necessarily as balanced as it could be. +

 

Two common types of balanced trees are red-black trees and AVL trees. 

 

 

Complete Binary Trees

A complete binary tree is a binary tree in which every level of the three is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right. 

 

Full Binary Tree

A full binary tree is a binary tree in which every node has either zero or two children. That is, no nodes have only one child.

Perfect Binary 

A perfect binary tree is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.

In an interview, do not assume a binary tree is perfect.