Trees

Trees are a fundamental data structure in computer science and have numerous applications in algorithms and problem-solving. A tree is a hierarchical structure composed of nodes connected by edges. It is similar to a family tree, where each node represents a person and the edges represent relationships between them.

Terminology

Before diving into the details of trees, let's familiarize ourselves with some common terminology:

• Node: Each element in a tree is called a node. Nodes can contain data or values.
• Root: The topmost node in a tree is called the root node. It serves as the entry point to the tree.
• Parent and Child: Nodes in a tree can have relationships, with one node being the parent of another node (directly connected below it). The node below is called the child of the parent node.
• Leaf: Nodes that do not have any children are called leaf nodes or terminal nodes.
• Subtree: A subtree is a smaller tree formed by a node and its descendants.

Tree Example

Let's consider a simple example of a binary tree:

1   1
2  / \
3 2   3

In the code above, we create a binary tree with three nodes. The root node has a value of 1 and has two child nodes - node 2 and node 3.

Understanding the structure and properties of trees is crucial for solving complex algorithms and efficiently storing and retrieving data. Let's explore various types of trees and their applications in the upcoming lessons.

xxxxxxxxxx

class Main {

  public static void main(String[] args) {

    // replace with your Java logic here

    TreeNode root = new TreeNode(1);

    TreeNode node1 = new TreeNode(2);

    TreeNode node2 = new TreeNode(3);

    root.left = node1;

    root.right = node2;

  }

}

​

class TreeNode {

  int val;

  TreeNode left;

  TreeNode right;

​

  TreeNode(int val) {

    this.val = val;

  }

}