Data Structures - Binary Search Trees
Home
>
Flashcards
> Print Preview
The flashcards below were created by user
javatomas
on
FreezingBlue Flashcards
. What would you like to do?
Get the free app for
iOS
Get the free app for
Android
Learn more
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
Card Set Information
Author:
javatomas
ID:
236029
Filename:
Data Structures - Binary Search Trees
Updated:
2013-10-16 05:44:45
Tags:
Trees Insert Delete
Folders:
Description:
Binary Search
Show Answers:
What would you like to do?
Get the free app for
iOS
Get the free app for
Android
Learn more
Home
>
Flashcards
> Print Preview