Scribd Logo
Upload

Welcome to Scribd!

  • 13 views

    Data Structure & Algorithm: Prepared By: Patrick V. Mole, MIT

    Uploaded by

    Loki Legends
    The document discusses binary trees, their terminology, types (full, complete), examples, and tree traversal methods (in-order, pre-order, post-order). It defines key concepts like root, parent, child, internal and leaf nodes. Binary trees have a maximum of two children per parent and every node has a left and right reference. Traversal involves visiting all nodes by starting at the root and following links in different orders.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Data Structure & Algorithm: Prepared By: Patrick V. Mole, MIT

    Uploaded by

    Loki Legends
    13 views18 pages
    The document discusses binary trees, their terminology, types (full, complete), examples, and tree traversal methods (in-order, pre-order, post-order). It defines key concepts like root, parent, child, internal and leaf nodes. Binary trees have a maximum of two children per parent and every node has a left and right reference. Traversal involves visiting all nodes by starting at the root and following links in different orders.

    Original Title

    Untitled

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses binary trees, their terminology, types (full, complete), examples, and tree traversal methods (in-order, pre-order, post-order). It defines key concepts like root, parent, child, internal and leaf nodes. Binary trees have a maximum of two children per parent and every node has a left and right reference. Traversal involves visiting all nodes by starting at the root and following links in different orders.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    13 views18 pages

    Data Structure & Algorithm: Prepared By: Patrick V. Mole, MIT

    Uploaded by

    Loki Legends
    The document discusses binary trees, their terminology, types (full, complete), examples, and tree traversal methods (in-order, pre-order, post-order). It defines key concepts like root, parent, child, internal and leaf nodes. Binary trees have a maximum of two children per parent and every node has a left and right reference. Traversal involves visiting all nodes by starting at the root and following links in different orders.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 18

    Data

    Structure &
    Algorithm
    Prepared by:
    Patrick V. Mole, MIT
    5
    Binary Tree
    Binary Tree Data Structure

     A binary tree is a tree-type non-linear data structure


    with a maximum of two children for each parent.
     Every node in a binary tree has a left and right
    reference along with the data element.
    Tree terminology
     Node: It represents a termination point in a tree.
     Root: A tree’s topmost node.
     Parent: Each node (apart from the root) in a tree that
    has at least one sub-node of its own is called a parent
    node.
     Child: A node that straightway came from a parent node
    when moving away from the root is the child node.
    Tree terminology (cont.)
     Leaf Node: These are external nodes. They are the
    nodes that have no child.
     Internal Node: As the name suggests, these are inner
    nodes with at least one child.
     Depth of a Tree: The number of edges from the tree’s
    node to the root is.
     Height of a Tree: It is the number of edges from the
    node to the deepest leaf. The tree height is also
    considered the root height.
    Tree terminology
    Node / Vertex
    A Root

    B C
    Left subtree
    Right subtree
    D F G

    Edges Leaves
    H I

    K M
    Example:

    Node A is the root. Nodes B and C are A’s children. Nodes B and D together form
    a subtree. Node B has two children: Its left child is the empty tree and its right
    child is D. Nodes A, C, and E are ancestors of G. Nodes D, E, and F make up level
    2 of the tree; node A is at level 0. The edges from A to C to E to G form a path of
    length 3. Nodes D, G, H, and I are leaves. Nodes A, B, C, E, and F are internal
    nodes. The depth of I is 3. The height of this tree is 3.
    Example Tree Calculations
    Recall: Height of a tree is the maximum number of A
    edges from the root to a leaf. Height = 4

    What is the height of this tree? B C

    A
    A D F G

    Height = 0 B Height = 1
    H I
    What is the depth of node G?
    Depth = 2
    K M
    Difference between Full &
    Complete Binary Tree

    Full Binary Tree


     A full binary tree is a binary tree
    in which all of the nodes have
    either 0 or 2 offspring.
     In other terms, a full binary
    tree is a binary tree in which all
    nodes, except the leaf nodes,
    have two offspring.
    Complete Binary Tree:
     When all of the levels of a
    binary tree are entirely filled,
    except for the last level, which
    can contain 1 or 2 children
    nodes and is filled from the left,
    it is said to be a complete binary
    tree.
    Example 1
     Node C has just one child
    therefore, it is not a Full binary
    tree.
     Node C also has a right child but
    no left child, therefore it is also
    not a Complete binary tree.
     Hence, the binary tree shown is
    neither complete nor full binary
    tree.
    Example 2
     All of the nodes have either 0 or 2
    offspring, therefore, it is a Full
    binary tree.
     It is not a Complete binary tree
    because node B has no children
    whereas node C has children, and
    according to a complete binary tree,
    nodes should be filled from the left
    side.
    Example 3

     It is a complete binary tree as all the nodes are left


    filled.
     Node B has just one child, therefore, it is not a full
    binary tree.
    Tree Traversal

     Traversal is a process to visit all the nodes of a tree and


    may print their values too.
     Because, all nodes are connected via edges (links) we
    always start from the root (head) node.
    Unlike linear data structures (Array, Linked List, Queues,
    Stacks, etc.) which have only one logical way to traverse
    them, trees can be traversed in different ways.

    There are three ways which we use to traverse a tree


     In-order Traversal
     Pre-order Traversal
     Post-order Traversal
    In-order Traversal (left subtree, root, right subtree)

    In this traversal method, the left subtree is visited first, then the
    root and later the right sub-tree.

    Algorithm
     Step 1 − Recursively traverse
    left subtree.
     Step 2 − Visit root node.
     Step 3 − Recursively traverse
    right subtree.

    OUTPUT: D → B → E → A → F → C → G
    Pre-order Traversal (root, left subtree, right subtree )

    In this traversal method, the root node is visited first, then the left
    subtree and finally the right subtree.

    Algorithm
     Step 1 − Visit root node.
     Step 2 − Recursively traverse
    left subtree.
     Step 3 − Recursively traverse
    right subtree.

    OUTPUT: A → B → D → E → C → F → G
    Post-order Traversal (left subtree, right subtree, root)

    In this traversal method, we first traverse the left subtree, then the
    right subtree and finally the root node.

    Algorithm
     Step 1 − Recursively traverse
    left subtree.
     Step 2 − Recursively traverse
    right subtree.
     Step 3 − Visit root node.

    OUTPUT: D → E → B → F → G → C → A

    You might also like