Binary search tree
1.Introduction
Each node in the left sub-tree of that node has a value less than or equal to the value of the node
Each node in the right sub-tree of that node has a value larger than or equal to the value of the node
Binary search tree are typically used for fast insertion and fast lookup
all left descendents <= n < all right descendents
2.Balanced v.s. Unbalanced
Balanced不一定只有左右子樹的size相同, 需再了解紅黑樹(red-black trees), AVL tree
以下為balanced tree的種類
Completed tree: child node先由左邊填起
Full binary tree:0或2個child node
Perfect tree:Completed tree + Full binary tree
3.Insertion
In a tree when a new code is added there is exactly one place that it can be
The structure of the tree depends on the order in which the nodes are added
The complexity for node insertion is O(Log n) in the average case
The actual complexity depends on the shape of the tree - skewed trees (IE. with all left or right children only) can have complexity of O(n)
跟head比大小, 小-> 跟左子繼續比; 大->跟右子繼續比, 當child為NULL時insert
public static Node<Integar> insert(Node<Integar> head, Node<Integar> node)
{
if (head == null)
{
return node;
}
if (node.getData() <= head.getData())
{
head.setLeftChild(insert(head.getLeftChild(), node));
}
else
{
head.setRightChild(insert(head.getRightChild(), node));
}
}
4.Lookup
While searching for a node in the tree there is only one place where that node can be found
We can simply follow the right or left sub-trees based on the value we want to find
The complexity for node lookup is O(Log n) in the average case
public static Node<Integar> Lookup(Node<Integar> head, int data)
{
if (head == null)
{
return nodenull;
}
if (head.getData() == data)
{
return head;
}
if (data <= head.getData())
{
return Lookup(head.getLeftChild(), data);
}
else
{
return Lookup(head.getRightChild(), data);
}
}
5.Minimum value in BST
public static int minimumValue(Node<Integar> head)
{
if (head == null)
{
return Integar.MIN_VALUE;
}
if (head.getLeftChild() == null)
{
return head.getData();
}
return minimumValue(head.getLeftChild());
}
6.Maximum depth of a binary tree
public static int maxDepth(Node root)
{
if (root == null)
{
return 0;
}
if (head.getLeftChild() == null && head.getRightChild() == null)
{
return 0;
}
int leftMaxDepth = 1 + maxDepth(root.getLeftChild());
int rightMaxDepth = 1 + maxDepth(root.getRightChild());
return Math.max(leftMaxDepth, rightMaxDepth);
}
7.Mirror a binary tree
public static void mirror(Node<Integer> root)
{
if (root == null)
{
return;
}
mirror(root.getLeftChild());
mirror(root.getRightChild());
Node<Integer> temp = root.getLeftChild();
root.setLeftChild(root.getRightChild());
root.setRightChild(temp);
}
8.Finding the structurally unique trees
public static int countTrees(int numNodes)
{
if (numNodes <= 1)
{
return 1;
}
int sum = 0;
for (int i = 1; i <= numNodes; i++)
{
int countLeftTrees = countTrees(i - 1);
int countRightTrees = countTrees(numNodes - 1);
sum = sum + (countLeftTrees * countRightTrees);
}
return sum;
}
9.Print all nodes within a range in a binary search tree
L -> V -> R
public static void printRange(Node<Integer> root, int low, int high)
{
if (root == null)
{
return;
}
if (low <= root.getData())
{
printRange(root.getLeftChild(), low, high);
}
if (low <= root.getData() && root.getData() <= high)
{
System.out.println(root.getData());
}
if (high > root.getData())
{
printRange(root.getRightChild(), low, high);
}
}
10.Check if a binary search tree
public static boolean isBinarySearchTree(Node<Integer> root, int min, int max)
{
if (root == null)
{
return true;
}
if (root.getData() <= min || root.getData() > max)
{
return false;
}
return isBinarySearchTree(root.getLeftChild(), min, root.getData()) &&
isBinarySearchTree(root.getRightChild(), root.getData(), max)
}
11.Path sum
public static boolean hasPathSum(Node<Integer> root, int sum)
{
if (root.getLeftChild() == null &&
root.getRightChild() == null)
{
return sum == root.getData();
}
int subSum = sum - root.getData();
if (root.getLeftChild() != null &&
hasPathSum(root.getLeftChild(), subSum))
{
return true;
}
if (root.getRightChild() != null &&
hasPathSum(root.getRightChild(), subSum))
{
return true;
}
return false;
}
12.Print all paths
public static boolean printPaths(Node<Integer> root, List<Node<Integer>> pathList)
{
if (root == null)
{
return;
}
pathList.add(root);
printPaths(root.getLeftChild(), pathList);
printPaths(root.getRightChild(), pathList);
if (root.getLeftChild() == null &&
root.getRightChild() == null)
{
print(pathList);
}
pathList(root);
}
13.Least common ancestor
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL)
{
return NULL;
}
if (root == p || root == q)
{
return root;
}
TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);
if (leftLCA != NULL && rightLCA != NULL)
{
return root;
}
if (leftLCA != NULL)
{
return leftLCA;
}
return rightLCA;
}
Last updated