Function _get_tree_properties

binarytree/__init__.py:1980–2055

Inspect the binary tree and return its properties (e.g. height). :param root: Root node of the binary tree. :type root: binarytree.Node :return: Binary tree properties. :rtype: binarytree.NodeProperties

(root: Node)

def _get_tree_properties(root: Node) -> NodeProperties:
    """Inspect the binary tree and return its properties (e.g. height).

    :param root: Root node of the binary tree.
    :type root: binarytree.Node
    :return: Binary tree properties.
    :rtype: binarytree.NodeProperties
    """
    is_descending = True
    is_ascending = True
    min_node_value = root.val
    max_node_value = root.val
    size = 0
    leaf_count = 0
    min_leaf_depth = 0
    max_leaf_depth = -1
    is_strict = True
    is_complete = True
    current_nodes = [root]
    non_full_node_seen = False

    while len(current_nodes) > 0:
        max_leaf_depth += 1
        next_nodes = []

        for node in current_nodes:
            size += 1
            val = node.val
            min_node_value = min(val, min_node_value)
            max_node_value = max(val, max_node_value)

            # Node is a leaf.
            if node.left is None and node.right is None:
                if min_leaf_depth == 0:
                    min_leaf_depth = max_leaf_depth
                leaf_count += 1

            if node.left is not None:
                if node.left.val > val:
                    is_descending = False
                elif node.left.val < val:
                    is_ascending = False
                next_nodes.append(node.left)
                is_complete = not non_full_node_seen
            else:
                non_full_node_seen = True

            if node.right is not None:
                if node.right.val > val:
                    is_descending = False
                elif node.right.val < val:
                    is_ascending = False
                next_nodes.append(node.right)
                is_complete = not non_full_node_seen
            else:
                non_full_node_seen = True

            # If we see a node with only one child, it is not strict