Binary Tree

Intro

Tree is an ADT that represents a hierarchical structure with a set of nodes and a set of edges that connect pairs of nodes and has the following properties:

• one node of the tree is designated as the root node
• every node N, except the root node, is connected by an incoming edge from exactly one other node P, where P is the parent of N
• a unique path traverses from any 2 vertices

An undirected and connected acyclic graph ⇒ there are no cycles or loops

Recursive Tree Definition

• a tree is either empty or consists of a root and zero or more subtrees, each of which is also a tree
• the root of each subtree is connected to the root of the parent tree by an edge

Subtree

• set of nodes and edges comprised of a parent and all the descendants of that parent
• a tree entirely contained within another

Binary Tree (BT) is a Tree for which

• every node has a maximum of two children

Binary Search Tree (BST)

Ternary / N-ary Trees

AVL Tree

The Little AVL Tree That Could

B Tree

Busying Oneself With B-Trees

Red-Black Tree

Painting Nodes Black With Red-Black Trees

AVL Tree

Segment Trees

Binary Indexed Tree

Root

• node in the tree that has no incoming edges
• it has no parent, although it may be useful to assign the parent of the root node to be itself e.g. filesystem tree
• a rooted tree
  • we have a reference to the root node of our tree
  • it does not always matter which node is selected to be the root node because any node can root the tree

Node

• a key
• additional information, called “payload”, usual in applications that make use of trees
• every node (except the root) is connected by exactly one incoming edge from another node
• each node may have several outgoing edges

Edge

• connects two nodes to show that there is a relationship between them

Path

• ordered list of nodes that are connected by edges

Children

• the set of nodes that have incoming edges from the same node are said to be the children of that node
• node extending another node

Parent

• a node is the parent of all the nodes it connects to with outgoing edges

Sibling

• nodes in the tree that are the children of the same parents

Leaf node

• node that has no children, a child-free parent node
• each leaf node is unique

Neighbour

• parent or child of a node

Ancestor

• node reachable by traversing its parent chain

Descendant

• node in the node's subtree

Degree

• number of children of a node
• degree of a tree = maximum degree of nodes in the tree

Distance

• number of edges along the shortest path between two nodes

Level/Depth

• number of edges along the unique path between a node and the root node

Height

• the height of a tree is the maximum level of any node in the tree

Width

• number of nodes in a level

Usage

• classification trees in biology
• to represent hierarchical data (e.g., file systems, directories or folders, web pages)

e.g. unix file system

e.g. html

Comparison

Problems

• [ ] Maximum Depth of Binary Tree
• [ ] Invert/Flip Binary Tree
• [ ] Same Tree
• [ ] Binary Tree Maximum Path Sum
• [ ] Binary Tree Level Order Traversal
• [ ] Lowest Common Ancestor of a Binary Tree
• [ ] Binary Tree Right Side View
• [ ] Subtree of Another Tree
• [ ] Construct Binary Tree from Preorder and Inorder Traversal
• [ ] Serialize and Deserialize Binary Tree
• [ ] Binary Tree Level Order Traversal
• [ ] Binary Tree InOrder Traversal
• [ ] Binary Tree PreOrder Traversal
• [ ] Implement Trie (Prefix Tree)

Code

Resources