There's an error in the function designed to check if a tree is a binary tree (not specifically a binary search tree)

There are several issues here:

• As you convert the dictionary representation of the graph to a binary tree (where each node has left and right attributes), it makes no sense to then check whether it is a binary tree, as of course it is: you created it as one. Note that:

  • you lose information when creating the second tree: there is no trace that node 'A' has child 'D' anymore, and so all three traversals omit 'D', even though it is a child of 'A' in the input.
  • The function that checks whether the tree is binary will never return False, as the preceding if clauses cover every possible case (given that your nodes only have left/right as child references)

• As all your verification functions already assume nodes with left/right children, they do not work for the general case, where nodes have possibly more than two children.

• It is not clear what an in-order traversal would mean for the second input: the concept of "in-order" is only well-defined for binary trees, not for general trees. You'd have to agree on some generalisation of that concept. You could for instance say that an internal node is visited after its first child and before any other children.

• Your tree creation function will get into an error if a node has just one child.

• The check for a complete tree is not correct. For instance, it will return True for this binary tree:

          A
         / \
        B   C
       / \
      D   E
     / \
    F   G
  

• It is not clear how the dictionary representation would define a binary tree that has nodes without a left child, like for instance this one:

          A
           \
            B
  

  In the dictionary you don't have a distinction between left and right, and so it would be just:

  {
      'A': ['B'],
      'B': None
  }
  

  You could agree to add a None inside the adjacency list to represent a missing left child, but this becomes awkward for when you have more than two children. For instance, what would this mean:

  {
      'A': [None, 'B', 'C'],
      'B': None,
      'C': None,
  }
  

  Is this not a binary tree, or is it? And if it is, then is 'B' a left child? We can imagine other weird things... This is not really a problem with your code, but just an observation that this input format does not seem well-defined (yet) for representing some binary trees.

Possible solution

I would suggest not to convert the input dictionary to some other structure. The dictionary is fine to work with as-is.

Here is a possible implementation, working directly with the dictionary representation.

Like you seemed to assume in your code, this code assumes that an input dictionary is guaranteed to represent a tree rooted in node 'A'. So: no cycles, for each node there is a key in the dictionary, all edges are directed (listed at the parent key in the dictionary), and there is exactly one root-to-node path for every node in the tree.

tree1 = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': None,
    'E': None,
    'F': None,
    'G': None
}

tree2 = {
    'A': ['B', 'C', 'D'],
    'B': None,
    'C': None,
    'D': None
}

def pre_order(tree, root):
    def order(node):
        yield node
        for child in tree[node] or []:
            yield from order(child)
    
    return [] if root is None else list(order(root))

def in_order(tree, root):
    def order(node):
        if tree[node]:
            yield from order(tree[node][0])
        yield node
        if tree[node]:
            for child in tree[node][1:]:
                yield from order(child)
    
    return list(order(root)) if tree else []

def post_order(tree, root):
    def order(node):
        for child in tree[node] or []:
            yield from order(child)
        yield node
        
    return list(order(root)) if tree else []


def tree_height(tree, root):
    def height(node):
        return 1 + max(map(height, tree[node] or []), default=-1)

    return height(root) if tree else -1

def is_binary_tree(tree):
    return not tree or all(not children or len(children) <= 2 for children in tree.values())

def is_full_tree(tree):
    return not tree or len(set(len(children) if children else 0 for children in tree.values())) <= 2

def is_complete_tree(tree, root):
    if not tree or len(tree) <= 1:
        return True
    degree = len(tree[root])
    
    # perform a breadth-first traversal
    q = [root]
    at_bottom = False
    for node in q:
        if tree[node] and (len(tree[node]) > degree or at_bottom):
            return False
        if not tree[node] or len(tree[node]) < degree:
            # As soon as one parent has not a complete set of children, no
            #   other parents (in BFS order) should have children
            at_bottom = True
        if tree[node]:
            q.extend(tree[node])

    return True


def count_nodes(tree):
    return len(tree)


def analyse_tree(tree, name, root):
    total_nodes = count_nodes(root)
    print(f"Tree {name}:")
    print("Pre-order:", pre_order(tree, root))
    print("In-order:", in_order(tree, root))
    print("Post-order:", post_order(tree, root))
    print("Height of the tree:", tree_height(tree, root))
    print("Is it a binary tree:", is_binary_tree(tree))
    print("Is it a full tree:", is_full_tree(tree))
    print("Is it a complete tree:", is_complete_tree(tree, root))
    print()

analyse_tree(tree1, "1", "A")
analyse_tree(tree2, "2", "A")