BST Flashcards
Tree
A tree represents a hierarchical relationship between nodes.
Root
The top node in a tree- has no parents.
Leaves
Nodes that have no children.
Interior Node
Any node that is not a root or a leaf.
Height of a Tree
The length of the lo gnest path from the root to a leaf in that tree.
Binary Tree
A tree in which each node can have a maximum of two children.
Full Binary Tree
Every node, other than the leaves, has two children.
Complete Binary Tree
Every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Tree Levels
The root of the tree is at level 0, the level of any other node in the tree is one more than the level of it’s parent.
Preorder Traversal
The root is visirted before it’s left and right subtrees.
Depth-First Search
DFS explores a path all the way to a leaf before backtracking and exploring another path.
Inorder Traversal
The root is visited between the subtrees.
Postorder Traversal
The root is visited after both subtrees.
Breadth-First Search (BFS)
BFS explores nodes nearest the root before exploring nodes further away.
Binary Search Tree Structure
The value of the node itself is larger than the value of every node in its left subtree and the value of the node itself is smaller thna the value of every node in its right subtree.
