Height of RPN Tree with Binary and Unary Nodes

Question

I know there is a way to get the depth of a pure binary RPN tree (e.g. here), but I am struggling to find out how to get the depth of a tree with binary and unary nodes.

For this problem, I am for the moment considering the following tokens: a set of binary operators '+', '-', '*', a set of unary operators 'cos', 'exp', and the leaf node 'x'. I have deduced that the tree I seek can have at most depth - 1 binary node, depth leaves and 0 unary nodes, or, at the other extreme, depth unary nodes, 0 binary nodes and 1 leaf node. Furthermore, I find that the number of leaves seems to always be the number of binary nodes + 1 in a valid RPN expression for my setting. However, I don't think this is a useful criterion for solving my problem, since simply changing the order of tokens can completely change the depth...

Nevertheless, I need to know the depth of an RPN expression with unary and binary nodes. As a bonus, it would be nice to know, if the RPN expression is incomplete (meaning it needs additional nodes added at the end to be complete) what the minimum depth at which the expression can be completed is.

Answer 1

First on your statement:

I have deduced that the tree I seek can have at most depth - 1 binary node, depth leaves

This is a mistake. Those maxima should be 2^depth−1 internal binary nodes, and 2^depth leaves.

The code you referenced can be easily extended to support unary operations. The principle is the same: a binary operator adds a root node whose height is determined by the highest subtree below it. As a unary operation has only one child tree below it, it is the highest, so no max is needed, and we can write stack.append(stack.pop() + 1) which really simplifies to stack[-1] += 1

def getRPNdepth(expression):
    stack = []
    for val in expression:
        if val in ['-', '+', '*', '/']:  # all binary operators
            stack.append(max(stack.pop(), stack.pop()) + 1)
        elif val in ['cos', 'exp']:  # all unary operators
            stack[-1] += 1
        else:  # an operand (x)
            stack.append(1)  
    return stack.pop()

Note that if the stack has more than one element before executing return stack.pop(), then the input expression is incomplete. If you want to know what the minimum height would be if the expression were completed, then repeat the action for a binary operator as many times as needed to end up with one item on the stack:

    while len(stack) > 1:
        stack.append(max(stack.pop(), stack.pop()) + 1)
        
    return stack.pop()