Tree Data Structure Intro
What is a tree data structure?
A tree is a hierarchical data structure consisting of nodes connected by edges. It has the following properties:
- One node is designated as the root node.
- Every node (except the root) is connected to exactly one parent node.
- Each node can have zero or more child nodes.
- Nodes with no children are called leaf nodes.
Why do we use tree data structures?
- Hierarchical Data Representation: Trees are used to represent data with hierarchical relationships, such as a file system.
- Efficient Searching: Trees like binary search trees (BST) allow for efficient searching, insertion, and deletion operations.
- Sorted Data: Trees like AVL trees and Red-Black trees maintain sorted data, allowing quick access and updates.
- Multi-way Trees: Trees like B-trees are used in databases and file systems for efficient data retrieval.
Practical use cases of tree data structures:
- File systems in operating systems.
- HTML DOM (Document Object Model) in web browsers.
- Family trees and organizational charts.
- Decision trees in machine learning.
- Abstract Syntax Trees in compilers.
- Trie data structure for efficient string searching.
- Binary Search Trees for maintaining sorted data.
Important Concepts in Tree Data Structure
1. Tree Terminology
- Node: Basic unit of a tree, containing data and links to children.
- Root: The top node in a tree.
- Edge: The link between two nodes.
- Child: A node directly connected to another node when moving away from the root.
- Parent: A node directly connected to another node when moving towards the root.
- Leaf: A node with no children.
- Subtree: A tree consisting of a node and its descendants.
- Height: The length of the longest path from the root to a leaf.
- Depth: The length of the path from the root to the node.
2. Types of Trees
- Binary Tree: Each node has at most two children.
- Binary Search Tree (BST): A binary tree with the left child less than the parent node and the right child greater than the parent node.
- AVL Tree: A self-balancing BST where the height of the two child subtrees of any node differ by at most one.
- Red-Black Tree: A self-balancing BST with additional properties for balancing.
- N-ary Tree: Each node can have at most N children.
- Segment Tree: Used for storing intervals or segments.
- Trie (Prefix Tree): Used for storing a dynamic set of strings.
3. Tree Traversals
Understanding different tree traversal methods is crucial:
- Inorder Traversal (Left, Root, Right): Used for BST to retrieve data in sorted order.
- Preorder Traversal (Root, Left, Right): Used to create a copy of the tree.
- Postorder Traversal (Left, Right, Root): Used to delete the tree.
- Level Order Traversal: Used for breadth-first traversal.
4. Common Operations
- Insertion: Adding a new node to the tree.
- Deletion: Removing a node from the tree.
- Searching: Finding a node in the tree.
- Balancing: Ensuring the tree remains balanced (e.g., AVL trees, Red-Black trees).
5. Applications of Trees
- Binary Search Trees (BST): Efficient searching, insertion, and deletion.
- Heaps: Priority queues.
- Tries: Autocomplete and spell checker.
- Segment Trees: Range queries.
BT implementation in more controable way using recursion
java
x
import java.util.LinkedList;import java.util.Queue;class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int val) { this.val = val; this.left = null; this.right = null; }}public class BinaryTree { TreeNode root; public BinaryTree() { root = null; } public void setRoot(int val) { root = new TreeNode(val); } public void addNode(int parentVal, int childVal, String position) { TreeNode parent = findNode(root, parentVal); if (parent != null) { if (position.equalsIgnoreCase("left")) { if (parent.left == null) { parent.left = new TreeNode(childVal); } else if (parent.left.val == childVal) { // Handle duplicate: add as left child of the existing node TreeNode newNode = new TreeNode(childVal); newNode.left = parent.left; parent.left = newNode; } else { // Recursively add to the left subtree addNode(parent.left.val, childVal, "left"); } } else if (position.equalsIgnoreCase("right")) { if (parent.right == null) { parent.right = new TreeNode(childVal); } else if (parent.right.val == childVal) { // Handle duplicate: add as left child of the existing node TreeNode newNode = new TreeNode(childVal); newNode.left = parent.right; parent.right = newNode; } else { // Recursively add to the right subtree addNode(parent.right.val, childVal, "right"); } } } else { System.out.println("Parent node not found"); } } private TreeNode findNode(TreeNode current, int val) { if (current == null || current.val == val) { return current; } TreeNode left = findNode(current.left, val); if (left != null) { return left; } return findNode(current.right, val); } public void levelOrderTraversal() { if (root == null) return; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode current = queue.poll(); System.out.print(current.val + " "); if (current.left != null) queue.add(current.left); if (current.right != null) queue.add(current.right); } } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.setRoot(1); tree.addNode(1, 2, "left"); tree.addNode(1, 3, "right"); tree.addNode(2, 4, "left"); tree.addNode(2, 5, "right"); tree.addNode(3, 6, "left"); tree.addNode(3, 7, "right"); // Adding a duplicate value tree.addNode(2, 5, "right"); System.out.println("Level Order Traversal:"); tree.levelOrderTraversal(); }}Code Output
Level Order Traversal:
1 2 3 4 5 6 7 5 This implementation provides the following features:
setRoot(int val): Sets the root of the tree.addLeft(int parentVal, int childVal): Adds a left child to a node with the given parent value.addRight(int parentVal, int childVal): Adds a right child to a node with the given parent value.findNode(TreeNode current, int val): A helper method to find a node with a given value.levelOrderTraversal(): Performs a level order traversal of the tree.
Basic Implementation Of Binary Tree
BT Basic Implementation
java
xxxxxxxxxximport java.util.LinkedList;import java.util.Queue;// Tree Node classclass TreeNode { int data; TreeNode left, right; public TreeNode(int item) { data = item; left = right = null; }}// Binary Tree classpublic class BinaryTree { TreeNode root; // Function to print level order traversal of tree void printLevelOrder() { Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (!queue.isEmpty()) { // Poll removes the present head. TreeNode tempNode = queue.poll(); System.out.print(tempNode.data + " "); // Enqueue left child if (tempNode.left != null) { queue.add(tempNode.left); } // Enqueue right child if (tempNode.right != null) { queue.add(tempNode.right); } } } public static void main(String args[]) { BinaryTree tree = new BinaryTree(); // Creating a sample tree: // 1 // / \ // 2 3 // / \ / \ // 4 5 6 7 tree.root = new TreeNode(1); tree.root.left = new TreeNode(2); tree.root.right = new TreeNode(3); tree.root.left.left = new TreeNode(4); tree.root.left.right = new TreeNode(5); tree.root.right.left = new TreeNode(6); tree.root.right.right = new TreeNode(7); System.out.println("Level order traversal of binary tree is - "); tree.printLevelOrder(); }}Code Output
Level order traversal of binary tree is -
1 2 3 4 5 6 7 
Planet Learning is a leading Ed Tech company striving to provide the best learning material on technical subjects.
© Copyright 2026. All Rights Reserved.