Trees

Vocabulary / Definition List

Node - A Tree node is a component which may contain its own values, and references to other nodes.
Root - The root is the node at the beginning 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 edge in a tree is the link between a parent and child node.
Leaf - A leaf is a node that does not have any children.
Height - The height of a tree is the number of edges from the root to the furthest leaf.
Traversing - Allows us to search for a node, print out the contents of a tree, and much more.
Depth First - This type of traversal is where we prioritize going through the depth (height) of the tree first. There are multiple ways to carry out depth first traversal, and each method changes the order in which we search / print the root.
Breadth first - This type of traversal iterates through the tree by going through each level of the tree node-by-node.
Binary Trees - Restrict the number of children to two. There is no specific sorting order for a binary tree. Nodes can be added into a binary tree wherever space allows
K-ary Trees - Nodes are able have more than 2 child nodes. We use K to refer to the maximum number of children that each Node is able to have.
Binary Search Trees - Type of tree that does have some structure attached to it. In a BST, nodes are organized in a manner where all values that are smaller than the root are placed to the left, and all values that are larger than the root are placed to the right.
Pre-order - Depth first traversal method that handles nodes in root » left » right order.
In-order - Depth first traversal method that handles nodes in left » root » right order.
Post-order - Depth first traversal method that handles nodes in left » right » root order.

source

-back