binary tree, represented by nested parentheses

Question

I'm new to python, I'm building a tree, this is my code:

class BinaryTree():
 def __init__(self, dado, left = None, right = None):
 self.dado = dado
 self.left = left
 self.right = right

I want to make a function to represent the binary tree, represented by nested parentheses. This function receives the root and shows, in one line, the structure of the elements. For example, the tree:

enter image description here

is displayed as (1 (2 () ()) (3 () (4 () ()))).

In this tree, the root of the tree is represented by the outermost parentheses, followed by the parentheses that encompass the left child (2 () ()) of the root, and then the parentheses that encompass the right child (3 () ( 4 () ) ( ))) from the root. The left node has no children ()() while the right node has a child (4()()), and this is also a leaf ()().

I tried to create the function but I couldn't leave it with the expected output... the result of my function comes out like this:

1
2
3
4

my code, trying to create a function, was this:

def show(node):
 string = [] 
 if not node: 
 return 
 print(node.dado)
 show(node.left) 
 show(node.right) 

• Josue Costa: shouldn't be there, I already organize the code
• Karl Knechtel: What part of your code could ever print a parenthesis?

Answer 1

You already implemented inorder traverse of your tree, which is good. You missed two things:

1. What do you want to print if node is null? -> empty brackets
2. What do you want to print before and after each step? -> brackets

So your function could look like that:

def show(node):
 if not node:
 print("()", end="")
 return
 print(f"({node.dado} ", end="")
 show(node.left)
 print(" ", end="")
 show(node.right)
 print(")", end="")

The end parameter of print prevent it to adding newline character at the end.

Answer 2

You should indeed use recursion for this, but your attempt is not adding any parentheses, and outputs line breaks.

For the base case -- when a node is None -- the string should be "()". When the node is not None, it is a matter of combining the recursive results of the two children with the node's own value.

Here is a function for that:

def serialize(node):
 if not node:
 return "()"
 return f"({node.dado} {serialize(node.left)} {serialize(node.right)})"

Here is how you could use it:

# Create tree that's used as example in the question
root = BinaryTree(1, BinaryTree(2), BinaryTree(3, None, BinaryTree(4)))
# Create the string for it
print(serialize(root)) # (1 (2 () ()) (3 () (4 () ())))

Answer 3

Yet another variation:

def show(node):
 print(end='(')
 if node:
 print(node.dado, end=' ')
 show(node.left)
 print(end=' ')
 show(node.right)
 print(end=')')