2

Suppose we have a tree and each node can have multiple children while the children can have more children etc.

Take this tree as an example:

- Node 1
    - Node 1.1
    - Node 1.2
        - Node 1.2.1
            - Node 1.2.1.1
            - Node 1.2.1.2
        - Node 1.2.2
    - Node 1.3
        - Node 1.3.1

Node 1 has a depth = 0 (root)

Node 1.1, 1.2, 1.3 has depth = 1 and so on

For each node I want to calculate the maximum depth it can reach. For example, Node 1 max. depth is 3 (the tree goes as deep as node 1.2.1.1). While Node 1.3 max depth = 1 (the subtree reaches as deep as node 1.3.1)

Now what I could do is to create a function, that takes a subtree and counts to the deepest node, and returns the depth value. But this would require calling that function for each and every node which seems very inefficient to me.

I want to create the tree and compute the max depths in one go.

I'm keeping the code very simple as there are a lot of other operations my function contains (such as generating new children as I'm building the tree from scratch, but I left these parts out for simplicity). But basically, I'm going through the tree like this:

def create_behavior_tree(depth, max_depth, behavior_tree)
  for child in behavior_tree.children:
    if depth > max_depth:
      max_depth = depth
    if len(child) > 0: # Expanding node
      max_depth = create_behavior_tree(depth + 1, max_depth, child)
      child.max_depth = max_depth  # problem: stores the values in "reverse"
    else: # Single node without children
      child.max_depth = depth


create_behavior_tree(1, 0, Tree)

However, when I do that, I can not reach the newest max_depth value for the outer node, it can only be reached within the innermost node (since this is recursion). So this would compute: Node 1 max depth = 0, Node 1.2 max depth = 1, Node 1.2.1 max depth = 2 etc. It's actually in reverse.

So, perhaps I need to use global variables here?

EDIT – A more detailed version of my function

def create_behavior_tree(depth, behavior_tree, children, max_tree_depth, node_count):
    if depth <= max_tree_depth:
        for child in children:
            # add behavior node
            if type(child) == Behaviour:
                behavior_tree.add_children([child])
                node_count += 1  # counting total nodes in tree
            # add composite node
            if type(child) == Composite:
                # replace by behavior node (reached max tree depth)
                if depth == max_tree_depth:
                    node = create_behaviour_node()
                    behavior_tree.add_children([node])
                    node_count += 1
                else:
                    behavior_tree.add_children([child])
                    node_count += 1
                    # further expand behavior tree 
                    children = create_random_children(size=3)
                    _, node_count = create_behavior_tree(depth + 1, node, children, max_tree_depth, node_count)
    return behavior_tree, node_count

random_children = create_random_children(size=3)  # Create 3 random children
root = py_trees.composites.Selector("Selector")

create_behavior_tree(1, root, random_children, 5, 0)
Improve this question
3
  • 1
    No global variables! Write a recursive function that takes a node as argument and returns the max. depth under that node. It should return 0 if there are no children, otherwise the 1 + max of the result of calling the function recursively on the children. Commented Dec 8, 2021 at 16:09
  • @MarkLavin that was my initial idea. however, when im creating the tree (through recursion), its already traversing through each node. isn't it possible to get these max values in that process all at once? Commented Dec 8, 2021 at 16:34
  • 1
    @ggorlen i edited my post. its 0 based (so if a node has no children, the max depth should be 0) Commented Dec 8, 2021 at 17:34

3 Answers 3

Reset to default
2

Taking advantage of the self-similarity of recursion, this is the same as any other one-pass O(n) depth/tree height algorithm, except set the maximum depth property for each node as you work back up the call stack:

def set_all_depths(tree):
    if not tree:
        return 0

    tree.max_depth = (
        max(map(set_all_depths, tree.children)) 
        if tree.children else 0
    )
    return tree.max_depth + 1

def print_tree(tree, depth=0):
    if tree:
        print("    " * depth + 
              f"{tree.val} [max_depth: {tree.max_depth}]")

        for child in tree.children:
            print_tree(child, depth + 1)


class TreeNode:
    def __init__(self, val, children=None, max_depth=None):
        self.val = val
        self.children = children or []
        self.max_depth = max_depth


if __name__ == "__main__":
    tree = TreeNode(
        "1",
        [
            TreeNode("1.1"),
            TreeNode(
                "1.2",
                [
                    TreeNode(
                        "1.2.1",
                        [
                            TreeNode("1.2.1.1"),
                            TreeNode("1.2.1.2"),
                        ],
                    ),
                    TreeNode("1.2.2"),
                ],
            ),
            TreeNode(
                "1.3",
                [
                    TreeNode("1.3.1"),
                ],
            ),
        ],
    )
    set_all_depths(tree)
    print_tree(tree)

Output:

1 [max_depth: 3]
    1.1 [max_depth: 0]
    1.2 [max_depth: 2]
        1.2.1 [max_depth: 1]
            1.2.1.1 [max_depth: 0]
            1.2.1.2 [max_depth: 0]
        1.2.2 [max_depth: 0]
    1.3 [max_depth: 1]
        1.3.1 [max_depth: 0]

Based on the follow-up comments, if you want to make the tree and assign max depths in one go, one way is to pick out the max depth from among the children and assign it to each node on the way back up the call stack.

Here's a library-agnostic proof of concept, since I don't have the classes you have in your new example:

import random
from random import randint


def make_random_tree(max_depth=4):
    if max_depth <= 0:
        return TreeNode(Id.make(), max_depth=0)

    node = TreeNode(Id.make())
    node.children = [
        make_random_tree(max_depth - 1) for _ in range(randint(0, 4))
    ]
    node.max_depth = 1 + (
        max([x.max_depth for x in node.children])
        if node.children else 0
    )
    return node

def print_tree(tree, depth=0):
    if tree:
        print("    " * depth + 
              f"{tree.val} [max_depth: {tree.max_depth}]")

        for child in tree.children:
            print_tree(child, depth + 1)


class TreeNode:
    def __init__(self, val, children=None, max_depth=None):
        self.val = val
        self.children = children or []
        self.max_depth = max_depth


class Id:
    identifier = 0

    def make():
        Id.identifier += 1
        return Id.identifier


if __name__ == "__main__":
    random.seed(1)
    tree = make_random_tree()
    print_tree(tree)

Output:

1 [max_depth: 4]
    2 [max_depth: 3]
        3 [max_depth: 1]
        4 [max_depth: 2]
            5 [max_depth: 1]
            6 [max_depth: 1]
                7 [max_depth: 0]
                8 [max_depth: 0]
                9 [max_depth: 0]
        10 [max_depth: 2]
            11 [max_depth: 1]
                12 [max_depth: 0]
                13 [max_depth: 0]
                14 [max_depth: 0]
            15 [max_depth: 1]
                16 [max_depth: 0]
                17 [max_depth: 0]
                18 [max_depth: 0]
            19 [max_depth: 1]
                20 [max_depth: 0]
        21 [max_depth: 1]

That said, assigning depths in a second pass is still O(n) so it might be premature optimization to do it all in one pass unless you have truly large or performance-critical code.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

this is actually what I was looking for. however, I'm having difficulties implementing this in my function (check out my newest edit). my tree is being generated randomly. so I dont pass an already created tree in the function. It takes a root node, then add 3 random children to it. then some of these children can be expanded again until a maximum tree depth is reached
It's the same algorithm whether you create the node on the spot or not. The max_depth can't be computed top-down; you have to pass that information back up the call stack, either as a separate return value, a property on one of the child nodes, a lookup table indexed by node.... It's probably easiest just to check a child node and see what max_depth it has and add 1 to it to compute the current node's max depth. If there are no child/current nodes as in the base case, the depth is 0 (depending on whether you're counting depth from 0 or 1).
Also, unless the tree is huge, it's just another pass to compute it as a separate step; still O(n). It might be premature optimization otherwise.
My comment two above might have been misleading: you want to take the max depth from all children. I updated the answer to cover this case in more detail, with proof of concept.
1

You can use a breadth-first search to get the depths for all nodes along with a path from the root to each node, and then iterates over the result for all nodes, producing maximum depths:

from collections import deque
tree = {'1': {'1': None, '2': {'1': {'1': None, '2': None}, '2': None}, '3': {'1': None}}}
def bfs(t):
   d = deque([(a, [a], 0, b) for a, b in t.items()])
   while d:
      yield (n:=d.popleft())[:-1]
      if n[-1] is not None:
         d.extend([(a, n[1]+[a], n[2]+1, b) for a, b in n[-1].items()])

nodes = list(bfs(tree))
r = {'.'.join(b):max(y for _, x, y in nodes if a in x) - c for a, b, c in nodes}

Output:

{'1': 3, '1.1': 2, '1.2': 2, '1.3': 1, '1.2.1': 1, '1.2.2': 1, '1.3.1': 1, '1.2.1.1': 0, '1.2.1.2': 0}
Improve this answer

Comments

0

I extended @ggorlen's answer if someone wants to also add information about the current depth of the node and how many nodes a node contains (counting nodes)

def create_depth_map(self, tree, depth, node_count):
    results = list(zip(*map(lambda x: self.create_depth_map(*x), [[child, depth + 1, node_count] for child in tree.children])))
    tree.max_depth = (max(results[0]) if tree.children else 0)
    tree.current_depth = depth
    node_count += (sum(results[1]) if tree.children else 0)
    tree.node_count = node_count
    return tree.max_depth + 1, node_count

so it will look like:

Selector [current_depth: 0] [max_depth: 5] [node_count: 17]
    Action [current_depth: 1] [max_depth: 0] [node_count: 1]
    Inverter [current_depth: 1] [max_depth: 3] [node_count: 7]
        Sequence [current_depth: 2] [max_depth: 2] [node_count: 6]
            Action [current_depth: 3] [max_depth: 0] [node_count: 1]
            Sequence [current_depth: 3] [max_depth: 1] [node_count: 4]
                Action [current_depth: 4] [max_depth: 0] [node_count: 1]
                Condition [current_depth: 4] [max_depth: 0] [node_count: 1]       
                Condition [current_depth: 4] [max_depth: 0] [node_count: 1]       
    Inverter [current_depth: 1] [max_depth: 4] [node_count: 8]
        Sequence [current_depth: 2] [max_depth: 3] [node_count: 7]
            Sequence [current_depth: 3] [max_depth: 2] [node_count: 5]
                Parallel [current_depth: 4] [max_depth: 1] [node_count: 3]        
                    Action [current_depth: 5] [max_depth: 0] [node_count: 1]      
                    Condition [current_depth: 5] [max_depth: 0] [node_count: 1]   
                Action [current_depth: 4] [max_depth: 0] [node_count: 1]
            Action [current_depth: 3] [max_depth: 0] [node_count: 1]

Thank you so much ggorlen this brought me further!

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.