WikiGalaxy
Tree Terminology
Node
A node is a fundamental part of a tree structure that contains data and links to other nodes, forming a hierarchy.
Root
The root is the topmost node in a tree. It serves as the starting point for traversing the tree.
Leaf
A leaf, or terminal node, is a node that does not have any children. It represents the end of a path in the tree.
Edge
An edge is a connection between two nodes. It represents the relationship between the parent and child nodes.
Height
The height of a tree is the length of the longest path from the root to a leaf. It indicates the maximum depth of the tree.
class TreeNode {
int data;
TreeNode left, right;
TreeNode(int item) {
data = item;
left = right = null;
}
}
Binary Tree Example
In a binary tree, each node has at most two children, referred to as the left child and the right child.
Balanced Tree
A balanced tree is a tree where the height difference between the left and right subtree for any node is not more than one.
Depth
Depth of a node is the number of edges from the root to the node. It measures how far a node is from the root.
Subtree
A subtree is a portion of a tree that consists of a node and all its descendants.
Binary Search Tree (BST)
A BST is a binary tree in which for each node, the left subtree contains only nodes with keys less than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key.
class BinaryTree {
TreeNode root;
BinaryTree() {
root = null;
}
}
Console Output:
Binary Tree Initialized
Tree Traversals
Inorder Traversal
In an inorder traversal, the nodes are recursively visited in this order: left, root, right.
Preorder Traversal
In a preorder traversal, the nodes are recursively visited in this order: root, left, right.
Postorder Traversal
In a postorder traversal, the nodes are recursively visited in this order: left, right, root.
Level Order Traversal
Level order traversal visits nodes level by level from top to bottom, left to right.
void inorderTraversal(TreeNode node) {
if (node == null)
return;
inorderTraversal(node.left);
System.out.print(node.data + " ");
inorderTraversal(node.right);
}
Example of Traversal
Inorder traversal of a binary search tree results in sorted order of the elements.
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.inorderTraversal(tree.root);
}
Console Output:
2 1 3
