juniorTrees

What is a tree data structure? Explain its basic terminology (root, parent, child, leaf, edge).

Updated Apr 28, 2026

Short answer

A tree is a non-linear data structure that organizes data in a hierarchical relationship using nodes connected by edges. It starts with a single top node called the root, and each node can have zero or more child nodes. Trees are used to represent relationships such as file systems, organization charts, and search structures.

Deep explanation

A tree data structure consists of nodes and edges. Unlike linear data structures such as arrays or linked lists, where elements are arranged in a sequence, a tree represents a hierarchy where one element can connect to multiple other elements.

A tree has the following characteristics:

  • It has exactly one root node, which is the starting point of the tree.
  • Every node except the root has exactly one parent node.
  • A node can have zero or more children.
  • Nodes with no children are called leaf nodes.
  • Nodes are connected using edges, which represent relationships between nodes.
  • A tree does not contain cycles, meaning you cannot start at a node and follow connections to return to the same node.

A simple tree structure can be visualized as:

TEXT
A
           /   \
          B     C
        /  \     \
       D    E     F

In this example:

  • A is the root because it is the topmost node.
  • B and C are children of A.
  • A is the parent of B and C.
  • D, E, and F are leaf nodes because they do not have any children.
  • The connections between A-B, A-C, B-D, B-E, and C-F are edges.

Basic Terminology

Root

The root is the topmost node in a tree. It is the only node that does not have a parent.

Example:

TEXT
Root
          A
        /   \
       B     C

A is the root node.

Parent

A parent is a node that has one or more child nodes connected below it.

Example:

TEXT
A
       / \
      B   C

A is the parent of B and C.

Child

A child is a node that is directly connected below another node.

Example:

TEXT
A
       /
      B

B is a child of A.

Leaf

A leaf is a node that has no children. It is the end point of a branch in a tree.

Example:

TEXT
A
       / \
      B   C

B and C are leaf nodes because they do not have any children.

Edge

An edge is the connection between two nodes in a tree. It shows the relationship between a parent and a child.

Example:

TEXT
A
       |
       B

The line connecting A and B is an edge.

Why Trees Are Useful

Trees are useful when data naturally has hierarchical relationships. They allow efficient searching, insertion, deletion, and organization of information.

Common types of trees include:

  • Binary Tree: Each node has at most two children.
  • Binary Search Tree (BST): A binary tree where left children contain smaller values and right children contain larger values.
  • Heap: A tree structure commonly used for priority queues.
  • Trie: A tree used for storing and searching strings efficiently.

The performance of tree operations depends on the type of tree and how balanced it is. For example, searching in a balanced binary search tree can take O(log n) time, while searching in a badly unbalanced tree may degrade to O(n).

Real-world example

A computer's file system is a common example of a tree structure.

TEXT
C:
              /      \
          Users     Program Files
            |
          Alice
         /     \
    Documents  Pictures

In this example:

  • C: is the root directory.
  • Users and Program Files are children of the root.
  • Alice is a child of Users.
  • Documents and Pictures are leaf nodes.

A simplified representation in code might look like:

Python
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []


root = TreeNode("C:")
users = TreeNode("Users")
programs = TreeNode("Program Files")


root.children.append(users)
root.children.append(programs)


users.children.append(TreeNode("Alice"))

This structure allows a program to easily navigate folders by moving from parent directories to child directories.

Common mistakes

  • * Confusing a tree with a graph
  • a tree is a special type of graph with no cycles and a single root.
  • * Assuming every tree node must have exactly two children
  • only binary trees have a maximum of two children.
  • * Forgetting that the root node has no parent.
  • * Calling every node without children a root
  • only the topmost node is the root.
  • * Assuming trees must always be displayed vertically
  • the layout is only a visual representation of the relationships.
  • * Ignoring the effect of tree balance on performance, especially in search trees.

Follow-up questions

  • What is the difference between a tree and a graph?
  • What is a binary tree?
  • How is a binary search tree different from a normal binary tree?
  • What is tree traversal?
  • Why does tree balance matter in a binary search tree?
  • Where are trees used in software systems?

More Trees interview questions

View all →