# Trees and Graphs Flashcards

Trees

Data structures with a root node and children nodes. Each child may also have children. The tree does not contain cycles.

Binary Trees

A tree in which each node has up to two children

Leaf Node

A node with no children.

Binary Search Tree

A binary tree in which every node fits a specific ordering property: left descendants <= n < all right descendants. This must be true for each node n and all of node n’s descendants, not just immediate children. Some binary search trees cannot have duplicates, others will have duplicates on the right, or either side.

Balanced Tree

Balanced enough to ensure O(log n) for insert and find, but not necessarily perfectly balanced.

Complete Binary Tree

A binary tree in which every level of the tree is completely filled, except for maybe the last level. Filling on the last level is from left to right.

Full Binary Tree

A binary tree in which every node has either zero or two children. No nodes have only one child.

Perfect Binary Tree

All Interior node have two children and all leaf nodes are at the same level.

Number of Nodes in a Perfect Binary Tree

The first level has 2**0, the second level has 2**1, the ith level has 2**(i-1) and the last level has 2**(N-1) where N is the depth of the tree. Total: 2**N - 1.

In-Order Binary Tree Traversal

Visit the left branch, then the current node, and finally, the right branch. When performed on a binary search tree, it visits the nodes in ascending order.

Implement In-Order Binary Tree Traversal

If node is not null, traverse the left child, then visit the center node, and then traverse the right child.

Pre-Order Binary Tree Traversal

Visits the current node before its child nodes. The root is always the first node visited.

Implement Pre-Order Binary Tree Traversal

if node is not null, visit the current node, traverse the left child node, then traverse the right child node.

Post-Order Tree Traversal

Visits the current node after its child nodes. The root is always the last node visited.

Implement Post-Order Tree Traversal

if node is not null, traverse the left child node, then traverse the right child node, then visit the current node.