↓Skip to main content
Algorithms

Trees

3 mins
Table of Contents

You Might Also Like

aerial view of a lush forest

What is a Tree? #

Trees are a type of data structure that are used to model many different mathematical structures. They are used in many different applications, including file systems and computer generated imagery.

Trees are a composed of nodes. The top node is called the root node, and the nodes that are connected to the root node are called children. For example, in a family tree, the root node would be the first person in the family tree, and their children would be the next generation of the family.

Tree Terminology #

The following table lists some common terms used to describe trees:

Term Definition Example
Node A fundamental unit of a tree, holding data and potentially connecting to other nodes. Imagine a person in a family tree, represented by a node containing their name and information.
Root The topmost node, with no parent, acting as the starting point of the tree. The oldest ancestor in a family tree would be the root node.
Edge The connection between one node and another. In a family tree, the edges would represent the relationships between family members.
Parent A node directly connected above another node, considered its ancestor. In a family tree, a parent node represents a child’s mother or father.
Child A node directly connected below another node, considered its *"descendant. Children in a family tree are child nodes relative to their parents.
Leaf A node without any children, marking the end of a branch. The youngest generation in a family tree typically consists of leaf nodes.
Sibling Nodes with the same parent, sharing a horizontal relationship. Siblings in a family tree are children of the same parent.
Subtree A tree consisting of a particular node and all its descendants. In a family tree, a particular branch starting from a specific ancestor can be considered a subtree.
E d g e N L o e d a e f N R o o d o e t E d g e N L o e d a e f N o d E e d g e N L o e d a e f E d g e

Each node is linked to other nodes by edges. The edges are the lines that connect the nodes. The root node is the only node that does not have a parent. All other nodes have exactly one parent.

A tree is graph that has no cycles.

Also note that a tree is a special type of graph. A graph is a collection of nodes and edges. A tree is a graph that has no cycles. A cycle is a path that starts and ends at the same node. In other words, a tree is a graph that has no loops.

What is a Tree Data Structure? #

A tree is a non-linear data structure that simulates a hierarchical tree structure with a set of connected nodes. Unlike arrays and linked lists, which are linear, trees allow for a hierarchical organization of data, making them ideal for scenarios where data is naturally hierarchical (like file systems) or when a quick search, insertion, and deletion are required.

In Java a a tree node can be represented as a class, which contains a value and a reference to its children. For a tree with a single interger value and multiple children, the class could be implemented as follows:

class TreeNode {
    int val;
    TreeNode[] children;
    TreeNode(int x) { val = x; }
}

Usage of this class to crate a tree with a root node and three children would look like this:

TreeNode root = new TreeNode(1);
TreeNode child1 = new TreeNode(3);
TreeNode child2 = new TreeNode(2);
TreeNode child3 = new TreeNode(4);
root.children = new TreeNode[] {child1, child2, child3};