# Tree

Last Updated: 2024-01-15

The most basic trees: Binary Tree and Binary Search Tree. For more advanced trees, like B-Tree, Merkel Tree, check Advanced Data Structures

## Tree Definition

### Java

``````class BinaryTree {

private Node root;

public BinaryTree() {
root = null;
}

private static class Node {
Node left;
Node right;
int data;

Node(int newdata) {
left = null;
right = null;
data = newdata;
}
}
}
``````

### Go

``````type Tree struct {
Left  *Tree
Value int
Right *Tree
}
``````

### Python

``````class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
``````

## Insert Into Binary Search Tree

``````public 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;
}
``````

## Traversal

In-order

``````public void inorder(Node node) {
if (node == null)
return;
inorder(node.left);
System.out.println(node.data);
inorder(node.right);
return;
}
``````

Pre-order

``````public void preorder(Node node){
if (node == null)
return;
System.out.println(node.data);
preorder(node.left);
preorder(node.right);
return;
}
``````

Post-order

``````public void postorder(Node node){
if (node == null)
return;
postorder(node.left);
postorder(node.right);
System.out.println(node.data);
return;
}
``````

## Min/Max Depth

``````public int maxDepth() {
return maxDepth(root);
}

public int maxDepth(Node node){
if (node == null)
return 0;
return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}

public int minDepth() {
return minDepth(root);
}

public int minDepth(Node node){
if (node == null)
return 0;
return 1 + Math.min(minDepth(node.left), minDepth(node.right));
}
``````

## Check Balance

``````public boolean isBalanced() {
return (maxDepth(root) - minDepth(root) <= 1);
}
``````

or

``````public boolean isBalanced(TreeNode root) {
return balanced(root) != -1;
}

private int balanced(TreeNode root) {
if (root == null) {
return 0;
}

int left = balanced(root.left);
int right = balanced(root.right);

if (left == -1 || right == -1) {
return -1;
}

if (Math.abs(left - right) <= 1) {
return Math.max(left, right) + 1;
} else {
return -1;
}
}
``````

## Has Path Sum

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);
}

public boolean hasPathSum(Node node, int sum) {
if (node == null) return (sum == 0);
return hasPathSum(node.left, sum - node.data) || hasPathSum(node.right, sum - node.data);
}
``````

## Size

``````public int size(Node node){
if (node == null)
return 0;
return 1 + size(node.left) + size(node.right);
}
``````

## Print Path

``````public void printPaths() {
int[] path = new int[size()];
printPaths(root, path, 0);
}

public void printPaths(Node node, int[] path, int len) {
if (node == null)
return;

path[len++] = node.data;
if (node.left == null && node.right == null) {
for (int i = 0; i < len; i++){
System.out.print(path[i] + " ");
}
System.out.println();
return;
} else {
printPaths(node.left, path, len);
printPaths(node.right, path, len);
}
}
``````

## Check Same

``````public boolean sameTree(Node a, Node b) {
if (a == null && b == null)
return true;
else if (a != null && b != null) {
return (a.data == b.data &&
sameTree(a.left, b.left) &&
sameTree(a.right, b.right));
} else {
return false;
}
}
``````

## Count Trees

For the key values 1...numKeys, how many structurally unique binary search trees are possible that store those keys?

Strategy: consider that each value could be the root. Recursively find the size of the left and right subtrees.

``````public static int countTrees(int n) {
if (n <= 1)
return 1;
int sum = 0;
for (int i = 1; i <= n; i++){
int left = countTrees(i-1);
int right = countTrees(n-i);
sum += left * right;
}
return sum;
}
``````

## IsComplete

``````import java.util.Arrays;
import java.util.Queue;

public class IsComplete {

class Node {
Node left, right;

public Node(Node left, Node right) {
this.left = left;
this.right = right;
}
}

public static boolean isComplete(Node root) {

queue.offer(root);

while (!queue.isEmpty()) {

// Stop as soon as we see first null
break;
}

}

// the remaining elements in the queue should all be null
while (!queue.isEmpty()) {