A tree in computer science is a data structure built from nodes that resembles the general structure of an upside down tree.
Properties
- Trees are constructed from nodes. Nodes may now have pointers to one or more other nodes.
- A set of nodes with a single starting point is the root of the tree.
- Each node is connected by an edge to another node (those edges are one-directional)
- A tree is a connected graph
- In a tree, every child has one parent (as opposed to in a graph)
- A leaf is a node with no children
- A binary tree is a tree with at most two children per node
Binary Tree
- A binary trees is perfect if all of it’s nodes have no or two nodes, and all leaves are at the same depth.
- In a perfect binary tree, each level doubles the number of nodes, which means that a perfect binary tree of height h has
- A binary tree is complete if
- the leaves are on at most two different levels
- the second to bottom level is completely filled in
- and the leaves on the bottom level are as far to the left as possible
- A Binary tree is full if
- every node has exactly 0 or 2 children.
Tree Height
The height of a tree is the amount of edges from the root of a tree to the furthest leaf of the tree.
Edge Cases
The height of a tree with one node is 0. The height of a tree with no nodes is -1.
Tree Depth
The depth of a node v is the length of the path from v to the root.
Other Types of Trees
Degenerate Trees
A degenerate tree, or spine, is a tree that is effectively a linked list, or a unary tree. This can happen in non-self balancing trees and is at the origin of many worst case linear time complexities for algorithms operating on non self-balancing trees.
Geeks4Geeks has a good article about it, and it’s a common topic of examination in CPSC 221.