DSA: Trees

Trie in DSA
What is Tree Data Structure?
  • A tree data structure is made up of nodes that are connected via edges.
  • The root node is the topmost node in a tree, and it is connected to zero or more child nodes.
  • Each child node can have zero or more child nodes attached to it, establishing a hierarchical structure.
  • Leaf nodes are nodes that have no child nodes.
  • Except for the root node, which has no parent node, each node in a tree can have only one parent node.
  • Siblings are nodes that share the same parent node.
  • The number of edges from the root node to a node is its depth, and the height of a tree is the maximum depth of any node in the tree.
Basic terms used in Tree data structure:

Some basic terms used in tree data structure are:

  1. Node: Each element in a tree is called a node.
  2. Node degree: The number of direct children of a node is called the degree of that node. For example, in the above tree, the degree of node 2 is 2 because it has two children.
  3. Root: The root node is the topmost node in the tree hierarchy. In other words, the root node is the one that doesn’t have any parent.
  4. Parent: The node which is one level above any node is called its parent i.e. If the node contains any sub-node, then that node is said to be the parent of that sub-node.
  5. Child: If the node is a descendant of any node, then the node is known as a child node.
  6. Siblings: Nodes that share the same parent are called siblings.
  7. Leaf: A node that does not have any children is called a leaf node or a terminal node.
  8. Subtree: A tree consisting of a node and all its descendants is called a subtree.
  9. Depth: The number of edges from the root to a given node is called its depth.
  10. Height: The number of edges on the longest path from a node to a leaf is called its height.
  11. Ancestor: A node that is on the path from the root to a given node is called an ancestor of that node.
  12. Descendant: A node that is below a given node in a tree is called a descendant of that node.
Implementation of Tree:

There are two main ways to implement trees: using an array and using linked lists.

  • Array Implementation: A binary tree is represented by an array in the array implementation. The root node is saved at index 1, the left child of a node at index i is stored at index 2i, and the right child of a node at index i is stored at index 2i+1. This technique is typically used for complete binary trees, where all levels but the last are filled.
class BinaryTree {
    int[] tree;
    int size;

    public BinaryTree(int size) {
        this.size = size;
        this.tree = new int[size + 1]; // add 1 for 1-indexing

    // insert a new node into the tree
    public void insert(int value) {
        if (size == tree.length - 1) {
            System.out.println("Tree is full.");
        tree[size] = value;

    // get the value of the parent node of a given index
    public int parent(int index) {
        return tree[index / 2];

    // get the value of the left child node of a given index
    public int leftChild(int index) {
        return tree[2 * index];

    // get the value of the right child node of a given index
    public int rightChild(int index) {
        return tree[2 * index + 1];

Time Complexity:O(1)
Space Complexity: O(n)

  • Linked List Implementation: Each node of the tree is represented as a separate object or node in the linked list implementation, having references or pointers to its sibling nodes. There are two kinds of linked list implementations:
  • Singly Linked List: Each node has a reference to only one child node, i.e., either the left child or the right child.
  • Doubly Linked List: Each node has references to both the left and the right child nodes.
public class TreeNode {
    int data;
    TreeNode leftChild;
    TreeNode rightChild;

    public TreeNode(int data) {
        this.data = data;
        this.leftChild = null;
        this.rightChild = null;

public class BinaryTree {
    TreeNode root;

    public BinaryTree() {
        root = null;

    public void insert(int data) {
        TreeNode newNode = new TreeNode(data);

        if (root == null) {
            root = newNode;
        } else {
            TreeNode current = root;
            TreeNode parent;

            while (true) {
                parent = current;

                if (data < current.data) {
                    current = current.leftChild;

                    if (current == null) {
                        parent.leftChild = newNode;
                } else {
                    current = current.rightChild;

                    if (current == null) {
                        parent.rightChild = newNode;

    public void printInorderTraversal(TreeNode node) {
        if (node != null) {
            System.out.print(node.data + " ");

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();


        System.out.print("Inorder Traversal: ");

Time Complexity: O(log n) to O(n) for insertion and O(n) for inorder traversal

Space Complexity: O(n)

Tree traversal techniques:

In tree data structure, there are two main traversal techniques:

  1. Depth-First Traversal: We study the deepest nodes of the tree data structure first, then progress up towards the root node in depth-first traversal. This technique is mostly used to investigate the structure of a tree.

There are three types of depth-first traversal:

  • Inorder Traversal: In inorder traversal, we first traverse the left subtree, then the root node and then the right subtree.
 public void inorderTraversal(Node node) {
        if (node == null) {
        System.out.print(node.data + " ");
  • Preorder Traversal: In preorder traversal, we first traverse the root node, then the left subtree and then the right subtree.
  public void printPreorder(Node node) {
        if (node == null)
        System.out.print(node.data + " ");
  • Postorder Traversal: In postorder traversal, we first traverse the left subtree, then the right subtree and then the root node.
void postorder(Node node) {
        if (node == null)
        // Traverse left subtree
        // Traverse right subtree
        // Visit root node
        System.out.print(node.data + " ");
  1. Breadth-First Traversal: In breadth-first traversal, we explore the level of the node by level starting from the root node. This technique is mostly used to locate a node or to determine the shortest path between two nodes.

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int value;
    Node left, right;
    Node(int value) {
        this.value = value;
        this.left = this.right = null;

public class BFS {
    Node root;
    BFS() {
        root = null;
    void printLevelOrder() {
        if (root == null)
        Queue<Node> queue = new LinkedList<Node>();
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.value + " ");
            if (node.left != null)
            if (node.right != null)
    public static void main(String[] args) {
        BFS tree = new BFS();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        System.out.println("BFS Traversal of Binary Tree:");

Time Complexity: O(n)

Space Complexity: O(n)

Note: also read about Problems based on Linked List

Follow Me

If you like my post please follow me to read my latest post on programming and technology.



Leave a Reply

Your email address will not be published. Required fields are marked *