Properties of Tree Data Structures

Learn Properties of Tree Data Structures with practical examples, explanations, best practices, and real-world coding techniques.

What Are Tree Properties?

Tree data structures follow a set of structural properties that distinguish them from other data structures and general graphs. These properties describe how nodes and edges are connected and help determine how tree algorithms behave.

Consider the following tree: 

              A
            /   \
           B     C
         /  \     \
        D    E     F
            / \
           G   H

This example contains eight nodes connected in a hierarchical structure. The properties of this tree can be used to describe its size, shape, connectivity, and relationships.

A Tree Is Connected

A tree is connected, meaning there is a path between every pair of nodes. Starting from the root, every other node in the tree can be reached by following edges. 

              A
            /   \
           B     C
         /  \     \
        D    E     F
            / \
           G   H

For example, there is a path from A to H: 

A → B → E → H

Because every node belongs to the same connected structure, this is a single tree rather than a collection of disconnected components.

A Tree Has No Cycles

A tree is acyclic. This means it does not contain a path that starts at a node, follows edges, and returns to that same node without repeating an edge or node along the cycle.

For example, the following structure is not a tree because it contains a cycle: 

      A
     / \
    B---C

A, B, and C form a closed loop. A valid tree cannot contain this kind of cycle.

A Tree With n Nodes Has n - 1 Edges

One of the most important properties of a tree is that a connected tree containing n nodes has exactly n - 1 edges. 

              A
            /   \
           B     C
         /  \     \
        D    E     F
            / \
           G   H

Nodes  = 8
Edges  = 7

Every time a new node is connected to an existing tree, one additional edge is required. Therefore, starting with one node and adding seven more nodes produces seven edges.

There Is Exactly One Simple Path Between Two Nodes

In a tree, exactly one simple path exists between any two nodes. This property follows from the fact that a tree is connected and contains no cycles.

For example, the path from D to H is: 

D → B → E → H

There cannot be another different path from D to H. If two different paths existed, they would create a cycle.

Adding an Edge Between Existing Nodes Creates a Cycle

If an additional edge is added between two existing nodes in a tree, a cycle is created. This happens because a path already exists between those two nodes. 

Tree:

    A
   / \
  B   C

Add edge B-C:

    A
   / \
  B---C

There is already a path B → A → C. Adding B → C creates a second path between B and C and therefore produces a cycle.

Removing Any Edge Disconnects the Tree

Every edge in a tree is necessary for maintaining connectivity. Removing one edge divides the tree into two separate connected components. 

Before:

      A
     / \
    B   C

Remove A-C:

      A
     /
    B

    C

The original tree is no longer connected after the edge is removed.

The Root Has No Parent

In a rooted tree, the root is the unique starting node and does not have a parent. Every other node has exactly one direct parent. 

              A
            /   \
           B     C
          / \
         D   E

Root:
A

Parent of B:
A

Parent of D:
B

This parent-child relationship gives a rooted tree its hierarchical structure.

Every Non-Root Node Has One Parent

In a standard rooted tree, each node other than the root has exactly one parent. A node may have zero or more children depending on the type of tree.

Node Parent Children
A None B, C
B A D, E
C A F
D B None

Leaf Nodes Have Degree Zero

A leaf node does not have any children. Therefore, its degree, defined as the number of children, is zero. 

              A
            /   \
           B     C
         /  \     \
        D    E     F

D, E, and F would be leaves only if they had no children. In the larger example used above, G and H are also leaves because they do not have children.

The Degree of a Tree Is the Maximum Node Degree

The degree of a node is its number of children. The degree of the entire tree is commonly defined as the largest node degree found anywhere in that tree. 

        A
      / | \
     B  C  D

Degree of A = 3
Degree of tree = 3

This distinction becomes especially useful when discussing general trees where a node can have more than two children.

Depth Depends on Distance From the Root

The depth of a node is commonly measured by the number of edges from the root to that node. The root has depth 0. 

              A        Depth 0
            /   \
           B     C      Depth 1
         /  \     \
        D    E     F    Depth 2
            / \
           G   H         Depth 3

Depth is a property of an individual node, not just the entire tree.

Tree Height Is the Maximum Depth

When height is measured in edges, the height of a rooted tree is the maximum depth of any node in that tree. 

              A
            /   \
           B     C
         /  \     \
        D    E     F
            / \
           G   H

Maximum depth = 3
Tree height   = 3

Height is therefore determined by the longest root-to-leaf path under this definition.

Subtrees Are Also Trees

A node together with all of its descendants forms a subtree. The resulting structure maintains the tree properties within that portion of the original tree. 

Original tree:

              A
            /   \
           B     C
         /  \
        D    E
            / \
           G   H

Subtree rooted at B:

        B
       / \
      D   E
         / \
        G   H

A Tree Is a Special Type of Graph

A tree can be viewed as a connected, acyclic graph. This relationship is important because many graph concepts and algorithms also apply to trees.

Property Tree General Graph
Connected Yes May or may not be
Cycles None May contain cycles
Edges for n nodes n - 1 No fixed value
Unique path Exactly one simple path May have multiple paths

A Tree Can Be Rooted at Different Nodes

The underlying tree structure does not necessarily depend on which node is chosen as the root. When a different node is selected as the root, parent-child relationships, depths, and heights can change. 

Original root:

    A
   / \
  B   C

Root = A


The same connected structure can be viewed from another root:

    B
    |
    A
    |
    C

Root = B

In algorithmic problems, the root is usually specified or implied by the problem. Changing it can change the calculated depth and height of nodes.

A Tree Can Be Balanced or Skewed

Trees can have different shapes. A balanced structure keeps branches relatively distributed, while a skewed tree has most nodes concentrated along one direction.

Relatively Balanced Tree

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

Skewed Tree

A
 \
  B
   \
    C
     \
      D

Tree shape matters because the height of a structure can directly affect the performance of operations in structures such as Binary Search Trees.

Binary Tree Properties

A binary tree is a specialized tree in which each node can have at most two children. These children are usually identified as the left child and right child. 

        A
       / \
      B   C
     / \
    D   E
  • Each node has at most two children.
  • A node may have zero, one, or two children.
  • The two possible child positions are left and right.
  • A binary tree does not automatically follow the ordering rules of a Binary Search Tree.

Important Tree Properties at a Glance

Property Meaning
Connected Every pair of nodes has a path between them
Acyclic The tree contains no cycles
Edges A tree with n nodes has n - 1 edges
Unique Path Exactly one simple path exists between two nodes
Root A rooted tree has one designated root with no parent
Leaf A node with no children
Depth Distance from the root to a node
Height Maximum downward distance to a leaf

Why Tree Properties Matter in Algorithms

Tree properties are not just definitions to memorize. They are used to reason about algorithms and prove why tree operations work.

For example, the unique-path property allows algorithms to move between two nodes without considering multiple alternative routes. The n - 1 edge property helps identify whether a connected graph can be a tree, while height helps explain the performance of operations in several tree-based structures.

Common Mistakes

  • Assuming every graph is a tree.
  • Forgetting that a tree cannot contain a cycle.
  • Assuming a tree can have more than n - 1 edges.
  • Confusing node degree with tree degree.
  • Confusing depth with height.
  • Assuming every tree must be balanced.
  • Assuming every tree is binary.
  • Assuming every binary tree is a Binary Search Tree.
  • Counting nodes instead of edges when calculating depth or height under an edge-based definition.

Key Takeaways

  • A tree is connected and acyclic.
  • A tree containing n nodes has exactly n - 1 edges.
  • There is exactly one simple path between any two nodes.
  • Adding an edge between existing nodes creates a cycle.
  • Removing any edge disconnects a tree into separate components.
  • In a rooted tree, the root has no parent and every other node has one parent.
  • Leaf nodes have no children and therefore have degree zero.
  • Tree height is determined by the longest downward path.
  • Subtrees preserve the tree structure within a portion of the original tree.
  • A binary tree allows each node to have at most two children.
  • Tree shape and height can affect the performance of tree-based algorithms.

Code Examples 

class Node {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
}

const root = new Node("A");
const b = new Node("B");
const c = new Node("C");
const d = new Node("D");

root.children.push(b, c);
b.children.push(d);

function countNodes(node) {
  if (node === null) {
    return 0;
  }

  let count = 1;

  for (const child of node.children) {
    count += countNodes(child);
  }

  return count;
}

const nodes = countNodes(root);
const edges = nodes - 1;

console.log("Nodes:", nodes);
console.log("Edges:", edges);
    
function height(node) {
  if (node === null || node.children.length === 0) {
    return 0;
  }

  let maxHeight = 0;

  for (const child of node.children) {
    maxHeight = Math.max(maxHeight, height(child));
  }

  return maxHeight + 1;
}

console.log("Height:", height(root));
    
function degree(node) {
  if (node === null) {
    return 0;
  }

  return node.children.length;
}

console.log("Degree of root:", degree(root));

Pro Tip

When analyzing a tree problem, first check its structural properties: whether it is connected, whether it contains cycles, how many nodes and edges it has, and what its height and degree are. These details often reveal which algorithm or traversal strategy fits the problem.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.