Binary Trees

BinaryTrees

Series of practice problems with solution code in Java. Binary trees have an elegant recursive pointer structure, so they are a good way to learn recursive pointer algorithms.

build123.java

/* This is a very basic problem with a little pointer manipulation. (You can skip this problem if you are already comfortable with pointers.) Write code that builds the following little 1-2-3 binary search tree... */

	public static TreeNode insert(TreeNode node, int data) {
		if (node == null) {
			node = new TreeNode(data);
		} else {
			if (data <= node.getData())
				node.setLeft(insert(node.getLeft(), data));
			else
				node.setRight(insert(node.getRight(), data));
		}
		return node;
	}

        public static TreeNode build123A() {
		TreeNode two = new TreeNode(2);
		TreeNode one = new TreeNode(1);
		TreeNode three = new TreeNode(3);

		two.setLeft(one);
		two.setRight(three);
		return two;
	}

	public static TreeNode build123B() {
		TreeNode two = new TreeNode(2);
		two.setLeft(new TreeNode(1));
		two.setRight(new TreeNode(3));
		return two;
	}

	public static TreeNode build123C() {
		TreeNode root = insert(null, 2);
		insert(root, 1);
		insert(root, 3);
		return root;
	}

doubleTree.java

/* For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree.
 So the tree... 
    2 
   / \ 
  1   3

 is changed to... 
       2 
      / \ 
     2   3 
    /   / 
   1   3 
  / 
 1

This can be accomplished without changing the root node pointer. */

	public static void doubleTree(TreeNode node) {
		if (node == null)
			return;
		int data = node.getData();
		TreeNode left = node.getLeft();
		TreeNode right = node.getRight();

		TreeNode newNode = new TreeNode(data);
		newNode.setLeft(left);
		newNode.setRight(null);
		node.setLeft(newNode);
		node.setRight(right);

		doubleTree(left);
		doubleTree(right);
	}

hasPathSum.java

/* 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.

Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found */

	public static boolean hasPathSum(TreeNode node, int sum) {
		if (node == null)
			return false;
		int currentSum = sum - node.getData();
		if (currentSum < 0)
			return false;
		if (isLeaf(node)) {
			if (currentSum == 0)
				return true;
			return false;
		} else {
			return hasPathSum(node.getLeft(), currentSum)
			    || hasPathSum(node.getRight(), currentSum);
		}
	}

InorderAndPostOrder.java

/* Given a binary search tree (aka an "ordered binary tree"), iterate over the nodes to print them out */

	public static void printInorder(TreeNode node) {
		if (node.getLeft() != null)
			printInorder(node.getLeft());
		System.out.print(node.getData() + " ");
		if (node.getRight() != null)
			printInorder(node.getRight());
	}

	public static void printPostOrder(TreeNode node) {
		if (node.getLeft() != null)
			printPostOrder(node.getLeft());
		if (node.getRight() != null)
			printPostOrder(node.getRight());
		System.out.print(node.getData() + " ");
	}

isBST.java

/* Version 1
Suppose you have helper functions minValue() and maxValue() that return the min or max int value from a non-empty tree. Write an isBST() function that returns true if a tree is a binary search tree and false otherwise. Use the helper functions, and don't forget to check every node in the tree. It's ok if your solution is not very efficient.

	public static int minValueNoBST(TreeNode node) {
		int min = node.getData();
		if (node.getLeft() != null)
			min = min(min, minValueNoBST(node.getLeft()));
		if (node.getRight() != null)
			min = min(min, minValueNoBST(node.getRight()));
		return min;
	}

	public static int maxValueNoBST(TreeNode node) {
		int min = node.getData();
		if (node.getLeft() != null)
			min = max(min, maxValueNoBST(node.getLeft()));
		if (node.getRight() != null)
			min = max(min, maxValueNoBST(node.getRight()));
		return min;
	}

	public static boolean isBST(TreeNode node) {
		int data = node.getData();
		TreeNode left = node.getLeft();
		TreeNode right = node.getRight();

		if (left != null) {
			if (data >= maxValueNoBST(left)) {
				return isBST(left);
			} else {
				return false;
			}
		}
		if (right != null) {
			if (data < minValueNoBST(right)) {
				return isBST(right);
			} else {
				return false;
			}
		}

		return true;
	}

Version 2

Version 1 above runs slowly since it traverses over some parts of the tree many times. A better solution looks at each node only once. The trick is to write a utility helper function that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX -- they narrow from there. */

	public static boolean isBSTRecur(TreeNode node, int min, int max) {
		if(node == null) return true;
		int data = node.getData();
		
		if(data < min || data > max) return false;
		return isBSTRecur(node.getLeft(), min, data) && isBSTRecur(node.getRight(), data, max);
	}

maxDepth.java

/* Given a binary tree, compute its "maxDepth" -- the number of nodes along the longest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0 */

	public static int maxDepth(TreeNode node) {
		int leftDepth = 0;
		int rightDepth = 0;
		if (node == null)
			return 0;
		else {
			leftDepth = maxDepth(node.getLeft());
			rightDepth = maxDepth(node.getRight());
		}
		return 1 + max(leftDepth, rightDepth);
	}

minAndMaxValues.java

/* Given a non-empty binary search tree (an ordered binary tree), return the minimum data value found in that tree. Note that it is not necessary to search the entire tree. A maxValue() function is structurally very similar to this function. This can be solved with recursion or with a simple while loop. */

	public static int minValue(TreeNode node) {
		if (node.getLeft() == null)
			return node.getData();
		else
			return minValue(node.getLeft());
	}

	public static int maxValue(TreeNode node) {
		if (node.getRight() == null)
			return node.getData();
		else
			return maxValue(node.getRight());
	}

mirror.java

/* Change a tree so that the roles of the left and right pointers are swapped at every node.
 So the tree... 
       4 
      / \ 
     2   5 
    / \ 
   1   3

 is changed to... 
       4 
      / \ 
     5   2 
        / \ 
       3   1

The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. Alternately, if you do not want to change the tree nodes, you may construct and return a new mirror tree based on the original tree. */

	public static void mirror(TreeNode node) {
		if (node == null)
			return;
		TreeNode left = node.getLeft();
		TreeNode right = node.getRight();

		node.setLeft(right);
		node.setRight(left);
		mirror(left);
		mirror(right);
	}

printPaths.java

/* Given a binary tree, print out all of its root-to-leaf paths as defined above. This problem is a little harder than it looks, since the "path so far" needs to be communicated between the recursive calls. */

	public static void printPaths(TreeNode node, List<Integer> path) {
		path.add(node.getData());
		if (isLeaf(node)) {
			System.out.print("Path: ");
			for (Integer n : path) {
				System.out.print(n + " ");
			}
			System.out.println();
		} else {
			if (node.getLeft() != null)
				printPaths(node.getLeft(), new ArrayList<Integer>(path));
			if (node.getRight() != null)
				printPaths(node.getRight(), new ArrayList<Integer>(path));
		}
	}

sameTree.java

/* Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way. */

	public static boolean sameTree(TreeNode a, TreeNode b) {
		if (a == null && b == null)
			return true;
		if (a != null)
			if (!a.equals(b))
				return false;
		return true;
	}

size.java

/* This problem demonstrates simple binary tree traversal. Given a binary tree, count the number of nodes in the tree. */
	
        public static int size(TreeNode node) {
		int count = 0;
		if (node != null) {
			count++;
			count += size(node.getLeft()) + size(node.getRight());
		}
		return count;
	}

TreeNode.java

package erni.trees;

public class TreeNode {
	
	private int data;
	private TreeNode left;
	private TreeNode right;
	
	TreeNode(int data) {
		this.data = data;
		this.left = null;
		this.right = null;
	}
	
	TreeNode getLeft() {
		return left;
	}
	
	TreeNode getRight() {
		return right;
	}
	
	int getData() {
		return data;
	}
	
	void setLeft(TreeNode left) {
		this.left = left;
	}
	
	void setRight(TreeNode right) {
		this.right = right;
	}
	
	@Override
	public boolean equals(Object obj) {
		boolean result = true;
		if(obj != null && obj instanceof TreeNode) {
			TreeNode node = (TreeNode) obj;
			TreeNode nodeLeft = node.getLeft();
			TreeNode nodeRight = node.getRight();
			
			if(node.getData() != this.data) return false;
			
			if(nodeLeft == null && left == null) result = true;
			else if(nodeLeft != null && left != null) {
				result = nodeLeft.equals(left);
			} else {
				return false;
			}
				
			if(nodeRight == null && right == null) return result && true;
			else if(nodeRight != null && right != null) {
				result = nodeRight.equals(right);
			} else {
				return false;
			}
		}
	  return result;
	}

}

Utils.java

	public static int max(int a, int b) {
		if (a > b)
			return a;
		return b;
	}

	public static int min(int a, int b) {
		if (a < b)
			return a;
		return b;
	}

	public static boolean isLeaf(TreeNode node) {
		return (node.getLeft() == null) && (node.getRight() == null);
	}