Tree

Binary Tree

Data Structure:

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} };

Full Binary Tree:

A binary tree is a full binary tree if every node has either 0 or 2 children.

(The above image is from http://alrightchiu.github.io/SecondRound/.)

Complete Binary Tree:

A binary tree is a complete binary tree if every level are completely filled except the last level. The last level can either completely filled or not.

(The above image is from http://alrightchiu.github.io/SecondRound/.)

Balanced Binary Tree:

A binary tree is a balanced binary tree if the height of the tree is O(longN), where N is the number of tree nodes.

(The above image is from https://algorithms.tutorialhorizon.com/.)