Trees Flashcards
Define a tree
A connected undirected graph with no cycles
Define a cycle
A path which starts and ends at the same node
Define connected in the frame of trees
There’s a path from any node to another node and there’s no node disconnected from others
Define undirected in the frame of trees
There is no direction associated with an edge
What’s the root of a tree?
The start node for traversals
What is a tree called if it has a root?
A rooted tree
What is a branch?
A path from the root to an end point
What is the end point of a branch called?
A leaf
What does the height of a tree describe?
The number of edges that connect the root node to the leaf node that is furthest away
What is the E, N equation?
E (number of edges) = N (number of nodes) -1
How are nodes connected in a rooted tree?
By parent-child relationships
What is a binary tree?
A rooted tree where every node has at most 2 child nodes
Why is a binary search tree different from a rooted tree?
It’s ordered to optimise searching
Describe a binary search tree
A rooted tree where the nodes of a tree are ordered
If the orders ascending the left nodes have values lower than the root and the right higher
How does an expression tree work?
Leaf nodes contain operands and other nodes contain operators
