30 Days of Algorithms: From Zero to Intermediate (12/30) — Binary Tree

A tree is a hierarchical data structure.

Data structures such as lists, queues, and stacks are linear. Their items are stored in a sequential way. However, a tree is a non-linear data structure because there is a parent-child relationship between the items.

Terminology

• Node — It is a fundamental building block that holds data and references to other nodes
• Root — It is the topmost node in the tree. In every tree there is always one unique root node
• Subtree — It's a smaller part of tree that’s contained entirely within a larger tree
• Degree — The total number of children a given node has
• Leaf node —It's a node that doesn't have any children. The degree of leaf node is always 0
• Edge — The connection between any two nodes. The number of edges in a tree is always one less than the number of nodes
• Sibling — Nodes with the same parent
• Level — It refers to vertical distance from the root node to any node. The level of root node is zero. The children of root node have level 1
• Height of a tree — It’s the number of edges from the root node to the farthest leaf node