Binary Tree: Basic knowledge and Coding Problems
-
Hits: 77044
Binary Tree: Coding Problems
Binary Tree is a data structure consisted of nodes containing data and two references to other nodes, one on the left and one on the right.
Binary Tree consist of Nodes
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
left = null;
right = null;
}
public setLeftNode(Node node){
this.left = node;
}
public setRightNode(Node node){
this.right = node;
}
}
Tree definitions:
- Binary Search Tree is a tree for all nodes the next rule works: left children value <= current node value <= right children value
- Balanced tree is a tree where the depth of the left and right subtrees of every node differ by 1 or less
- Full Binary Tree is a tree every node other than the leaves has two children
- Perfect Binary Tree is a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children
- Complete Binary Tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible
- Heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node. Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. In Java, PriorityQueue is important to know.
Java Binary Tree Structure
public class BinaryTree {
private Node root; // Root node pointer. Will be null for an empty tree.
private static class Node {
Node left;
Node right;
int data;
Node(int newData) {
left = null;
right = null;
data = newData;
}
}
// Create empty binary tree
public void BinaryTree() {
root = null;
}
public void insert(int data) {
root = insert(root, data);
}
private Node insert(Node node, int data) {
if (node==null) {
node = new Node(data);
}
else {
if (data <= node.data) {
node.left = insert(node.left, data);
}
else {
node.right = insert(node.right, data);
}
}
return(node); // in any case, return the new pointer to the caller
}
}
Operations
Insert(int n) : Add a node with value n O(lgn)
Find(int n) : Find a node with value n O(lgn)
Delete (int n) : Delete a node with value n O(lgn)
Display(): Prints the entire tree in increasing order O(n)
Classic Tree problems
Most of the solutions use two methods: a one-line OOP method that starts the computation, and a recursive method that does the real operation.
Size
Returns the number of nodes in the tree
public int size() {
return(size(root));
}
private int size(Node node) {
if (node == null) return(0);
else {
return(size(node.left) + 1 + size(node.right));
}
}
Max Depth
Returns the max root-to-leaf depth of the tree
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);
return(Math.max(lDepth, rDepth) + 1);
}
}
Min value
Returns the min value in a non-empty binary search tree
public int minValue() {
return( minValue(root) );
}
private int minValue(Node node) {
Node current = node;
while (current.left != null) {
current = current.left;
}
return(current.data);
}
Max value
Returns the max value in a non-empty binary search tree
public int maxValue() {
return( maxValue(root) );
}
private int maxValue(Node node) {
Node current = node;
while (current.right != null) {
current = current.right;
}
return(current.data);
}
Inorder print of tree
Prints the node values in the "inorder" order
public void printInOrderTree() {
printInOrderTree(root);
System.out.println();
}
private void printInOrderTree(Node node) {
if (node == null) return;
// left, node itself, right
printInOrderTree(node.left);
System.out.print(node.data + " ");
printInOrderTree(node.right);
}
Postorderprint of tree
Prints the node values in the "postorder" order
public void printPostOrderTree() {
printPostOrderTree(root);
System.out.println();
}
private void printPostOrderTree(Node node) {
if (node == null) return;
printPostOrderTree(node.left);
printPostOrderTree(node.right);
System.out.print(node.data + " ");
}
PreOrder print of tree
Recursion
Prints the node values in the "preorder" order
public void printPreOrderTree() {
printPreOrderTree(root);
System.out.println();
}
private void printPreOrderTree(Node node) {
if (node == null) return;
System.out.print(node.data + " ");
printPreOrderTree(node.left);
printPreOrderTree(node.right);
}
Without recursion (Traversal)
public class Solution {
public ArrayList<Integer> preorderTraversal(Node root) {
ArrayList<Integer> returnList = new ArrayList<Integer>();
if(root == null)
return returnList;
Stack stack = new Stack();
stack.push(root);
while(!stack.empty()){
TreeNode n = stack.pop();
returnList.add(n.val);
if(n.right != null){
stack.push(n.right);
}
if(n.left != null){
stack.push(n.left);
}
}
return returnList;
}
public void print(Node root){
ArrayList<Integer>
list = preorderTraversal(root);
for(Integer item: list){
System.out.println(item.data);
} }
}
Print in Level order (Traversal)
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
4
/ \
8 22
/ \
11 6
return its level order traversal as [[4], [8,22], [11,6]]
public ArrayList<ArrayList> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> al = new ArrayList<ArrayList<Integer>>();
ArrayList nodeValues = new ArrayList();
if(root == null)
return al;
LinkedList current = new LinkedList();
LinkedList next = new LinkedList();
current.add(root);
while(!current.isEmpty()){
TreeNode node = current.remove();
if(node.left != null)
next.add(node.left);
if(node.right != null)
next.add(node.right);
nodeValues.add(node.data);
if(current.isEmpty()){
current = next;
next = new LinkedList();
al.add(nodeValues);
nodeValues = new ArrayList();
}
}
return al;
}
Has Path Sum (Traversal)
Given a tree and a sum, returns true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum.
public boolean hasPathSum(int sum) {
return( hasPathSum(root, sum) );
}
boolean hasPathSum(Node node, int sum) {
// return true if we run out of tree and sum==0
if (node == null) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node.data;
return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum));
}
}
Binary Tree: Coding Problems
Binary Tree is a data structure consisted of nodes containing data and two references to other nodes, one on the left and one on the right.
Binary Tree consist of Nodes
class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
left = null;
right = null;
}
public setLeftNode(Node node){
this.left = node;
}
public setRightNode(Node node){
this.right = node;
}
}
Tree definitions:
- Binary Search Tree is a tree for all nodes the next rule works: left children value <= current node value <= right children value
- Balanced tree is a tree where the depth of the left and right subtrees of every node differ by 1 or less
- Full Binary Tree is a tree every node other than the leaves has two children
- Perfect Binary Tree is a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children
- Complete Binary Tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible
- Heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then the key (the value) of node A is ordered with respect to the key of node B with the same ordering applying across the heap. A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node. In a min heap, the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node. Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm, and in the sorting algorithm heapsort. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. In Java, PriorityQueue is important to know.
Java Binary Tree Structure
public class BinaryTree {
private Node root; // Root node pointer. Will be null for an empty tree.
private static class Node {
Node left;
Node right;
int data;
Node(int newData) {
left = null;
right = null;
data = newData;
}
}
// Create empty binary tree
public void BinaryTree() {
root = null;
}
public void insert(int data) {
root = insert(root, data);
}
private Node insert(Node node, int data) {
if (node==null) {
node = new Node(data);
}
else {
if (data <= node.data) {
node.left = insert(node.left, data);
}
else {
node.right = insert(node.right, data);
}
}
return(node); // in any case, return the new pointer to the caller
}
}
Operations
Insert(int n) : Add a node with value n O(lgn)
Find(int n) : Find a node with value n O(lgn)
Delete (int n) : Delete a node with value n O(lgn)
Display(): Prints the entire tree in increasing order O(n)
Classic Tree problems
Most of the solutions use two methods: a one-line OOP method that starts the computation, and a recursive method that does the real operation.
Size
Returns the number of nodes in the tree
public int size() {
return(size(root));
}
private int size(Node node) {
if (node == null) return(0);
else {
return(size(node.left) + 1 + size(node.right));
}
}
Max Depth
Returns the max root-to-leaf depth of the tree
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);
return(Math.max(lDepth, rDepth) + 1);
}
}
Min value
Returns the min value in a non-empty binary search tree
public int minValue() {
return( minValue(root) );
}
private int minValue(Node node) {
Node current = node;
while (current.left != null) {
current = current.left;
}
return(current.data);
}
Max value
Returns the max value in a non-empty binary search tree
public int maxValue() {
return( maxValue(root) );
}
private int maxValue(Node node) {
Node current = node;
while (current.right != null) {
current = current.right;
}
return(current.data);
}
Inorder print of tree
Prints the node values in the "inorder" order
public void printInOrderTree() {
printInOrderTree(root);
System.out.println();
}
private void printInOrderTree(Node node) {
if (node == null) return;
// left, node itself, right
printInOrderTree(node.left);
System.out.print(node.data + " ");
printInOrderTree(node.right);
}
Postorderprint of tree
Prints the node values in the "postorder" order
public void printPostOrderTree() {
printPostOrderTree(root);
System.out.println();
}
private void printPostOrderTree(Node node) {
if (node == null) return;
printPostOrderTree(node.left);
printPostOrderTree(node.right);
System.out.print(node.data + " ");
}
PreOrder print of tree
Recursion
Prints the node values in the "preorder" order
public void printPreOrderTree() {
printPreOrderTree(root);
System.out.println();
}
private void printPreOrderTree(Node node) {
if (node == null) return;
System.out.print(node.data + " ");
printPreOrderTree(node.left);
printPreOrderTree(node.right);
}
Without recursion (Traversal)
public class Solution {
public ArrayList<Integer> preorderTraversal(Node root) {
ArrayList<Integer> returnList = new ArrayList<Integer>();
if(root == null)
return returnList;
Stack stack = new Stack();
stack.push(root);
while(!stack.empty()){
TreeNode n = stack.pop();
returnList.add(n.val);
if(n.right != null){
stack.push(n.right);
}
if(n.left != null){
stack.push(n.left);
}
}
return returnList;
}
public void print(Node root){
ArrayList<Integer>
list = preorderTraversal(root);
for(Integer item: list){
System.out.println(item.data);
} }
}
Print in Level order (Traversal)
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
4
/ \
8 22
/ \
11 6
return its level order traversal as [[4], [8,22], [11,6]]
public ArrayList<ArrayList> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> al = new ArrayList<ArrayList<Integer>>();
ArrayList nodeValues = new ArrayList();
if(root == null)
return al;
LinkedList current = new LinkedList();
LinkedList next = new LinkedList();
current.add(root);
while(!current.isEmpty()){
TreeNode node = current.remove();
if(node.left != null)
next.add(node.left);
if(node.right != null)
next.add(node.right);
nodeValues.add(node.data);
if(current.isEmpty()){
current = next;
next = new LinkedList();
al.add(nodeValues);
nodeValues = new ArrayList();
}
}
return al;
}
Has Path Sum (Traversal)
Given a tree and a sum, returns true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum.
We'll define a "root-to-leaf path" to be a sequence of nodes in a tree starting with the root node and proceeding downward to a leaf (a node with no children). We'll say that an empty tree contains no root-to-leaf paths. So for example, the following tree has exactly four root-to-leaf paths:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1
For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27.
public boolean hasPathSum(int sum) {
return( hasPathSum(root, sum) );
}
boolean hasPathSum(Node node, int sum) {
// return true if we run out of tree and sum==0
if (node == null) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node.data;
return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum));
}
}
Print Paths
Given a binary tree, prints out all of its root-to-leaf paths, one per line.
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
Paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1
public void printPaths() {
int[] path = new int[1000];
printPaths(root, path, 0);
}
private void printPaths(Node node, int[] path, int pathLen) {
if (node==null) return;
// append this node to the path array
path[pathLen] = node.data;
pathLen++;
// it's a leaf, so print the path that led to here
if (node.left==null && node.right==null) {
printArray(path, pathLen);
}
else {
// otherwise try both subtrees
printPaths(node.left, path, pathLen);
printPaths(node.right, path, pathLen);
}
}
private void printArray(int[] ints, int len) {
int i;
for (i=0; i<len; i++) {
System.out.print(ints[i] + " ");
}
System.out.println();
}
Create mirror of the tree
Changes the tree into its mirror image.
So the tree...
4
/ \
2 5
/ \
1 3
is changed to...
4
/ \
5 2
/ \
3 1
public void mirror() {
mirror(root);
}
private void mirror(Node node) {
if (node != null) {
// do the sub-trees
mirror(node.left);
mirror(node.right);
// swap the left/right pointers
Node temp = node.left;
node.left = node.right;
node.right = temp;
}
}
Update tree as a double tree
Changes the tree by inserting a duplicate node on each nodes's .left.
So the tree...
2
/ \
1 3
Is changed to...
2
/ \
2 3
/ /
1 3
/
1
public void doubleTree() {
doubleTree(root);
}
private void doubleTree(Node node) {
Node oldLeft;
if (node == null) return;
// do the subtrees
doubleTree(node.left);
doubleTree(node.right);
// duplicate this node to its left
oldLeft = node.left;
node.left = new Node(node.data);
node.left.left = oldLeft;
}
Median or kth element
Finding kth element in BST is quite simple. We know that all the elements in left subtree is smaller than all the elements in right subtree. If we count the number of elements in left and right subtree then we know in which subtree the required element exists and then we move to this subtree and repeat the same steps again. For example starting from root we are looking for 11th element. Lets say left subtree has 7 elements and right subtree has 6 elements.Then as the number 11 is greater than 7 we know that the 11th median exists in the right subtree. Now in the right subtree we look for (11 - 7 -1 = 3)rd element (Why?? because we have discarded left subtree). We proceed similarly in the new subtree until we get the kth median as the root.
The example described above can very well be described in recursive form. The code below is a complete program in recursive form.
//find kth element in a BST recursively
Node find_kth_element(Node tree, int k) {
if(tree == null)
return null;
int count = 0;
//count the nodes in left subtree
count_nodes(tree.left, count);
//check if the root is median
if( k == count + 1)
return tree;
//check if median falls on left subtree
else if (count >= k) {
return find_kth_element(tree.left,k);
}
//the median falls on right subtree
else {
k = k - (count + 1);
return find_kth_element(tree.right, k);
}
}
We know that recursive solutions are not that efficient and it's always good to avoid it if it's possible. The problem however is equally simple in iterative form as well. The code below translates recursive form into iterative form.
//find kth element iteratively
Node find_kth_element_iterative(Node tree, int k) {
if(tree == null)
return null;
Node node = tree;
int count = 0;
int pos = k;
while(node != null) {
count = 0;
//count nodes on the left subtree
count_nodes(node.left, count);
//check if root is the median
if( pos == count + 1)
return node;
//check if median falls on left subtree
else if (count >= pos)
node = node.left;
//median falls on right subtree
else {
pos -= (count + 1);
node = node.right;
}
}
return null;
}
What's the complexity of above algorithms? While finding median You are moving along a path in the tree, so in the worst case it can be height of the tree (h) and also you are counting the number of nodes in left subtree at each step. Which requires O(n) time in the worst case. Thus the overall algorithm is O(nh).
How can you improve it? You can construct a tree with a count of elements in its subtree. If you do this the counting of number of nodes in left subtree takes O(1) time. Effectively the algorithm will reduce to O(h) algorithm. In case tree is balanced this is just O(log n).
public String median() {
int count = root.left.size + root.right.size + 1;
count = (int) Math.floor(count/2);
System.out.println("count="+count);
return median(root, count);
}
private String median(Node n, int count) {
if (n.size == count) return n.key;
if (n.left!=null && n.right!=null)
return median(n.left,count) + median(n.right,count);
if (n.left!=null)
return median(n.left,count);
if (n.right!=null)
return median(n.right,count);
return"";
}
Number of null nodes
public int numNull() {
return numNull(root);
}
private int numNull(Node n) {
if (n==null) return 1;
return numNull(n.left) + numNull(n.right);
}
Length of the shortest path from root to a null node
Way 1: Recursion
public int lenShortestPathToNull() {
return lenShortestPathToNull(root);
}
public int lenShortestPathToNull(Node node) {
if (node==null) return 1;
return Math.min(lenShortestPathToNull(node.left), lenShortestPathToNull( node.right));
}
Way 2: Loop
public class Item {
public Node node;
public int count;
private Item(Node node, int count) {
this.node = node;
this.count = count;
}
}
public int lenShortestPathToNull() {
if (root==null) new IllegalArgumentException("Illegal argument");
int count = 0;
Node cur = root;
LinkedList queue = new LinkedList();
Item item = new Item(root, 0);
queue.add(item);
while(queue.size()!=0){
Item n = queue.poll();
if (n.node.left == null) return n.count;
if (n.node.right == null) return n.count;
item = new Item(n.node.left, n.count+1);
queue.add(item);
item = new Item(n.node.right, n.count+1);
queue.add(item);
}
return 0;
}
Merge of two binary trees
If the given symbol table contains keys that is already in this symbol table, merge overwrites those keys' values with the values in the given symbol table.
public void merge(BST bst) {
merge(bst.root);
}
public void merge(Node n) {
put(n.key, n.val);
if (n.left!=null) merge(n.left);
if (n.right!=null) merge(n.right);
}
public void put(String key, Integer val) {
if (key == null) throw new NullPointerException("first argument to put() is null");
root = put(root, key, val);
}
private Node put(Node x, String key, Integer val) {
if (x == null) return new Node(key, val);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, val);
else if (cmp > 0) x.right = put(x.right, key, val);
else x.val = val;
x.size = 1 + size(x.left) + size(x.right);
return x;
}
Return closest key from BST
public String closest(String key) {
if (key=="" || key==null || root==null) return null;
if (get(key)!=null) return (key);
ArrayList arr= new ArrayList();
closest(root, key, arr);
int min=Integer.MAX_VALUE;
String kkey =null;
Collections.sort(arr);
for(String item: arr){
if (min>Math.abs(key.compareTo(item))) {
kkey = item;
min = Math.abs(key.compareTo(item));
}
}
//recursion
return kkey;
}
public void closest(Node node, String key, ArrayList arr) {
if (node.key.compareTo(key)<0) {
// go to right side
if (node.right== null) {
//last node, which may be a parent; no pair
if (arr.size()==0) arr.add(node.key);
return;
}
else { if (node.right.key.compareTo(key)>0) {
// add pair if key may be between nodes keys
arr.add(node.key);
arr.add(node.right.key);
if (node.right.left!=null) {
//try to find new sides
closest(node.right.left, key, arr);
} else {
//we are good, no additional pairs; just return
return;}
}
else {
// no pair, both node's keys smaller than our key
closest(node.right, key, arr);
}
}
} else {
if (node.left== null) {if (arr.size()==0) arr.add(node.key); return;}
else { if (node.left.key.compareTo(key)<0) {
// add pair if key may be between nodes keys
arr.add(node.key);
arr.add(node.left.key);
if (node.left.right!=null) closest(node.left.right, key, arr); else return; }
else closest(node.left, key, arr);
}
}
}
Second max key
public String SecondMax(){
if (root==null) return null;
return SecondMax(root, null, null);
}
public String SecondMax(Node n, String max, String secondMax){
if (n==null || n.key==null) return secondMax;
if (max==null || max.compareTo(n.key)<0)
{secondMax = max;
max = n.key;}
else {
if (secondMax==null || secondMax.compareTo(n.key)<0)
secondMax=n.key;
}
if (n.right!=null)
return SecondMax(n.right, max, secondMax);
else
return SecondMax(n.left, max, secondMax);
}