Data Structures with Generic Types in Python/

...

/

BinaryTree: A Basic Binary Tree

BinaryTree: A Basic Binary Tree

Learn BinaryTree implementation.

We'll cover the following...

The simplest way to represent a node, u, in a binary tree is to explicitly store the (at most three) neighbours of u:

Press + to interact
class BinaryTree(object):
    class Node(object):
        def __init__(self):
            self.left = self.right = self.parent = None
    def __init__(self):
        super(BinaryTree, self).__init__()
        self.nil = None
        self.r = None
        self.initialize()

When one of these three neighbours is not present, we set it to None. In this way, both external nodes of the tree and the parent of the root correspond to the value None.

The binary tree itself can then be represented by a reference to its root node, r:

Press + to interact
class BinaryTree(object):
    class Node(object):
        def __init__(self):
            self.left = self.right = self.parent = None
    def __init__(self):
        super(BinaryTree, self).__init__()
        self.nil = None
        self.r = None
        self.initialize()
        
    def initialize(self):
        self.r = None

We can compute the depth of a node, u, in a binary tree by counting the number of steps on the path from u to the root:

Press + to interact
class BinaryTree(object):
    class Node(object):
        def __init__(self):
            self.left = self.right = self.parent = None
    def __init__(self):
        super(BinaryTree, self).__init__()
        self.nil = None
        self.r = None
        self.initialize()
        
    def depth(self, u):
        d = 0
        while (u != self.r):
            u = u.parent
            d += 1
        return d

Recursive algorithms

Using recursive algorithms makes it very easy to compute facts about binary trees. For example, to compute the size of (number of nodes in) a binary tree rooted at node u, we recursively compute the sizes of the two subtrees rooted at the children of u, sum up these sizes, and add one:

Press + to interact
class BinaryTree(object):
    class Node(object):
        def __init__(self):
            self.left = self.right = self.parent = None
    def __init__(self):
        super(BinaryTree, self).__init__()
        self.nil = None
        self.r = None
        self.initialize()
    
    def _size(self, u):
        if u == self.nil: return 0
        return 1 + self._size(u.left) + self._size(u.right)

To compute the height of a node u, we can compute the height of u’s two subtrees, take the maximum, and add one:

Press + to interact
class BinaryTree(object):
    class Node(object):
        def __init__(self):
            self.left = self.right = self.parent = None
    def __init__(self):
        super(BinaryTree, self).__init__()
        self.nil = None
        self.r = None
        self.initialize()
        
    def _height(self, u):
        if u == self.nil: return 0
        return 1 + max(self._height(u.left), self._height(u.right))

Traversing binary trees

The two algorithms from the previous section both use recursion to visit all the ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy