Tree Algorithms
In this section, we will explore different algorithms related to trees. These algorithms are commonly used to solve problems involving trees and can help us find important information about the structure of a tree.
Finding the Height of a Tree
The height of a tree is the number of edges from the root to the deepest leaf node. It represents the maximum number of levels in the tree. To find the height of a tree, we can use a depth-first search (DFS) algorithm.
Here's a Java code snippet that shows how to find the height of a tree using a recursive DFS approach:
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5
6 public TreeNode(int val) {
7 this.val = val;
8 this.left = null;
9 this.right = null;
10 }
11}
12
13public class Main {
14 public static int getHeight(TreeNode root) {
15 if (root == null) {
16 return -1;
17 }
18 int leftHeight = getHeight(root.left);
19 int rightHeight = getHeight(root.right);
20 return Math.max(leftHeight, rightHeight) + 1;
21 }
22
23 public static void main(String[] args) {
24 // Replace with your Java code here
25 }
26}Finding the Diameter of a Tree
The diameter of a tree is the length of the longest path between any two nodes in the tree. It represents the maximum distance between any two nodes.
To find the diameter of a tree, we can use a combination of depth-first search (DFS) and recursion.
Here's a Java code snippet that shows how to find the diameter of a tree using DFS and recursion:
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5
6 public TreeNode(int val) {
7 this.val = val;
8 this.left = null;
9 this.right = null;
10 }
11}
12
13public class Main {
14 public static int getDiameter(TreeNode root) {
15 if (root == null) {
16 return 0;
17 }
18 int leftHeight = getHeight(root.left);
19 int rightHeight = getHeight(root.right);
20 int leftDiameter = getDiameter(root.left);
21 int rightDiameter = getDiameter(root.right);
22 int currentDiameter = leftHeight + rightHeight + 2;
23 return Math.max(currentDiameter, Math.max(leftDiameter, rightDiameter));
24 }
25
26 public static void main(String[] args) {
27 // Replace with your Java code here
28 }
29}Finding the Lowest Common Ancestor
The lowest common ancestor (LCA) of two nodes in a tree is the deepest node that is an ancestor of both nodes. It represents the common parent node of the two given nodes. To find the LCA, we can use a bottom-up approach and traverse the tree from the root to the leaves.
Here's a Java code snippet that shows how to find the lowest common ancestor of two nodes in a binary tree:
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5
6 public TreeNode(int val) {
7 this.val = val;
8 this.left = null;
9 this.right = null;
10 }
11}
12
13public class Main {
14 public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
15 if (root == null || root == p || root == q) {
16 return root;
17 }
18 TreeNode left = lowestCommonAncestor(root.left, p, q);
19 TreeNode right = lowestCommonAncestor(root.right, p, q);
20 if (left != null && right != null) {
21 return root;
22 }
23 if (left != null) {
24 return left;
25 }
26 if (right != null) {
27 return right;
28 }
29 return null;
30 }
31
32 public static void main(String[] args) {
33 // Replace with your Java code here
34 }
35}xxxxxxxxxxclass Main { public static void main(String[] args) { // Replace with your Java code here }}