Home
Flashcards
Preview
Data Structures - Binary Search Trees
Home
Get App
Take Quiz
Create
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.
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
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
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
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());
What is a depth of a node?
The length of the path from the root to the node.
What is the height of a node?
The length of the path from that node to the deepest node.
What is the size of a node?
The number of descendants it has including itself.
What are skew trees?
Every node in a tree has only one child.
When is a binary tree is referred to as a strict binary tree?
If each node has exactly 2 children or no children.
What is a full binary tree?
If each node has exactly 2 children and all leaf nodes are at same level.
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.
Preorder traversal
V
alue-
L
eft-
R
ight
Postorder traversal
L
eft-
R
ight-
V
alue
Author
javatomas
ID
236029
Card Set
Data Structures - Binary Search Trees
Description
Binary Search
Updated
2013-10-16T05:44:45Z
Show Answers
Home
Flashcards
Preview