Data Structures - Binary Search Trees

Card Set Information

Author:
javatomas
ID:
236029
Filename:
Data Structures - Binary Search Trees
Updated:
2013-10-16 01:44:45
Tags:
Trees Insert Delete
Folders:

Description:
Binary Search
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user javatomas on FreezingBlue Flashcards. What would you like to do?


  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

What would you like to do?

Home > Flashcards > Print Preview