Intro DS: Trees & Binary Trees

Trees and Binary Trees


The following explanation of Trees is taken from Wikipedia:




In computer science, a tree is a widely used abstract data type (ADT) or data structure implementing this ADT that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linkednodes.


A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.


Below is an example of a Binary Tree. It is considered binary because none of the nodes have more than two children. In this diagram 8 is the root node value. The nodes containing 1, 4, 7, and 13 are referred to as the leaf nodes of the tree. A leaf node is a node with no children.