Trees

Types

• Binary Trees,
• Binary Search Trees
• K-ary Trees.

Terminology

• Node - A Tree node includes its own values and the references to other nodes
• Root - the beginning node of the tree
• K - A number that specifies the maximum number of children any node may have in a k-ary tree.
• Left - A reference to one child node, in a binary tree
• Right - A reference to the other child node, in a binary tree
• Edge - The link between a parent and child node
• Leaf - A leaf is a node that does not have any children
• Height - The number of edges from the root to the furthest leaf

Traversal

• Depth First (DFS)
• Breadth First (BFS) (picture credit: Vaidehi Hoshi from medium.com)

Binary tree vs k-ary trees vs binary search tree

• binary tree: a tree in which each node can have at most two children. Typically the first node is known as the parent and the child nodes are called left and right.
• A binary search tree:ma binary tree in which the nodes are assigned values, with the following restrictions:
  • No duplicate values
  • Left child node is smaller than its parent Node
  • Right child node is greater than its parent Node
• K-ary tree: A rooted tree with each node has no more than m children. a general binary tree with K = 2