- Open Bookshelf Cover Page
- Preface
- Getting Started
- Introduction to Recursion
- Divide and Conquer Algorithms
- Dynamic Programming
-
Binary Trees
- Intro to Trees
- Binary Trees
- Types of Binary Trees
- Divide & Conquer in Tree Problems
- Practice: Binary Tree Height
- Tree Traversal: DFS and BFS
- Practice: Preorder Traversal
- Practice: Inorder Traversal
- Practice: Postorder Traversal
- Practice: Level Order Traversal
- Binary Search Tree
- Practice: Find Node in a BST
- Graphs
- Backtracking
- Conclusion
- Share on
Introduction to Trees
Trees are a fundamental abstract data structure in computer science used to represent hierarchical relationships between elements. They consist of nodes connected by edges. This lesson will introduce the basics of trees, including their terminology and structure.
Terminology
To effectively discuss trees, it's important to understand the specific terms used to describe their components and characteristics:
- Nodes: These are the basic units of a tree. Each node contains data, which can be a number, a string, or any other data type. Think of nodes as the individual points on a tree branch.
-
Edges: An edge connects two nodes together and defines the hierarchy of our tree. As can be seen in our diagrams, edges have direction. Node
1has no incoming edges, but two outgoing edges that point to nodes2and5. Node5has one incoming edge from node1, and no outgoing edges.
-
Root: The root of the tree is the node without a parent, similar to the base of a real tree. It is the topmost node from which all other nodes descend. In our example, node
1is the root.
-
Parent and Child Nodes: In a tree, any node can be a parent or a child node, except for the root, which can only be a parent. A parent node is one that has branches (edges) leading to other nodes. For instance, node
2is the parent of nodes3and4. A child node is one that is the continuation of a branch (an incoming edge) from a parent node, so nodes3and4are children of node2.
-
Leaf Nodes: These are nodes that do not have any children. They are like the leaves on a real tree, which are the endpoints of the smallest branches. In our tree, nodes
3,4, and5are leaf nodes as they have no children.
-
Levels and Height: The level of a node is determined by its distance from the root, with the root being at level
0. The height of the tree is the level of the deepest node or the longest path from the root to a leaf node. In this case, the height is2.
In the following assignment, we will delve into a specific type of tree called the Binary Tree.