Tree Nodes Flashcards
A leaf node is a node…
that has no children
True or False.
Any node with a child is an internal node
True
How many children can a node have in a binary tree?
It can have up to 2 children
What is the depth of a root node?
0
If a tree has just one node what is the depth?
0
A link from a node to a child is called a…
edge
A binary tree is full if…
Every node contains 0 or 2 children
A binary tree is perfect if…
All internal nodes have 2 children and all leaf nodes are at the same level
A binary tree is complete if…
All levels, except the last level, contain all possible nodes and all nodes in the last level are as far left possible
What is a binary search tree?
Orders the left child of the less than or equal to the parent node
Orders the right child greater than or equal to the parent node
Where does searching begin in a tree?
It begins at the root
Example: If you are searching for 145 in a tree and the root of the node is 300, where will the search begin?
145< 300, so the search will begin with the left child
If a match is not found what is returned?
Null
Insert as a node as a left child involves…
If the new node is less than the current node
The current nodes left child is null
Insert a node as a right child involves…
If the new node’s key is greater than or equal to the current node
The current node right child is null
Searching for an insert location involves…
If the right or left child is not null
The algorithm assigns the current node with that child and continues looking for a proper location
What is a tree traversal?
Visits all the nodes in the tree and performs an operation on each node
What is an inorder traversal?
Visits all the nodes in a BST from smallest to largest
What is the algorithm for in order traversal?
left current right
What is the height of a tree?
Is the maximum number of edges from the root of the tree
If a tree’s height is N=7, what is the height?
h - 1 = 7 - 1 = 6
Therefore the answer is 6.
How can you implement a search using recursion?
A base case is checking if the node is not null
If the key is equal to the node
If the key is less than
node–> key return
What is a preorder traversal?
Starts at the root node than works its way down the left side of child then the right side
Moves on to the right side of the tree and goes through the left children than the right children
What is inorder traversal?
Starts on the left subtree than the root node then moves on to the right subtree
What is post order traversal?
Starts on the left subtree than the right sub tree and then the root node
What does the find(key) method do?
Returns the reference to node containing key if present
What does the findMin() do?
Returns the node containing the smallest key
What does the findMax() do?
Returns the node containing the largest key
What does add(key) do?
Inserts a new node in tree at correct position(unless already present)
What does remove(key) do?
Removes key from tree if present
