Data Structures - Binary Search Trees

The flashcards below were created by user javatomas on FreezingBlue Flashcards.

1. What is considered a binary tree?
If each node has 0 child, 1 child or 2 children. Empty trees is also a valid binary tree.
2. Keys in deleting a node in a tree
Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.

Deleting a node with one child: Remove the node and replace it with its child.

Deleting a node with two children
3. Deleting a leaf
• left child node = parent's left node
• right child node = parent's right node

• Check if the left child's node is NULL && right child's node is NULL
• then set parent's left node = null
4. Deleting a node with one child
• left child node = parent's left node
• right child node = parent's right node

• if the left child's left node is null then
• set the parent's left node to it's left child's right node

• if the left child's right node is null then
• set the parent's left node to it's left child's left node
5. Deleting a node with 2 children
• left child node = parent's left node
• right child node = parent's right node

set the parent's left node to it's left child's right node

and

leftChildNode.getRightNode().setLeftNode(leftChildNode.getLeftNode());
6. What is a depth of a node?
The length of the path from the root to the node.
7. What is the height of a node?
The length of the path from that node to the deepest node.
8. What is the size of a node?
The number of descendants it has including itself.
9. What are skew trees?
Every node in a tree has only one child.
10. When is a binary tree is referred to as a strict binary tree?
If each node has exactly 2 children or no children.
11. What is a full binary tree?
If each node has exactly 2 children and all leaf nodes are at same level.
12. What is a complete Binary Tree?
If all leaf nodes are at height h or h-1 and also without any missing number in the sequence.
13. Preorder traversal
Value-Left-Right
14. Postorder traversal
Left-Right-Value
 Author: javatomas ID: 236029 Card Set: Data Structures - Binary Search Trees Updated: 2013-10-16 05:44:45 Tags: Trees Insert Delete Folders: Description: Binary Search Show Answers: