# How to create tree from struct

I want to create tree with struct. Here’s my approach:

``````mutable struct node{T}
data::T
left::node
right::node
node(T)= (data=T; left= Nothing; right= Nothing)
end

root=node(1)
root.left=node(2)
root.right=node(3)
root.right.left=node(4)
root.right.right=node(5)
``````

, but it doesn’t work. Later I want also create function to compute the “height” of a tree, that means the number of nodes along the longest path from the root node down to the farthest leaf node.
That would be something like that:

``````function height(root)
if root === Nothing
return 0
else
lheight = height(root.left)
rheight = height(root.right)
if lheight > rheight
return lheight+1
else
return rheight+1
end
end
end
end
``````

and all the level and order printing functions.

``````mutable struct node{T}
data::T
left::Union{node, Nothing}
right::Union{node, Nothing}
node(T)= (data=T; left= Nothing; right= Nothing)
end
``````

You need to make left/right a Union of node and Nothing so you can assign nothing to it.

5 Likes

First of all, inner constructor of `node` is not quite correct, since you try to store type instead of data itself. Secondly you do not need to use `Nothing` to distinguish between initialized and not initialized nodes, since you can use incomplete initialization. You may find these links useful: inner constructor and
incomplete initialization. So, your example can be rewritten as

``````mutable struct node{T}
data::T
left::node
right::node
node(x::T) where T = new{T}(x)
end

function height(root)
lheight = isdefined(root, :left) ? height(root.left) : 0
rheight = isdefined(root, :right) ? height(root.right) : 0
return max(lheight, rheight) + 1
end
``````

So, as you can see

``````root = node(1)
# node{Int64}(1, #undef, #undef)
``````

and for `height` function:

``````root = node(1)
root.left = node(2)
root.right = node(3)
root.right.left = node(4)
root.right.right = node(5)

height(root)
# 3
``````
3 Likes

Of course you can use your original approach, but it would be more suitable to apply multiple dispatch:

``````mutable struct node{T}
data::T
left::Union{Nothing, node}
right::Union{Nothing, node}
end

node(x::T) where T = node{T}(x, nothing, nothing)

height(root::Nothing) = 0
height(root) = max(height(root.left), height(root.right)) + 1
``````

Note also, that while type is `Nothing` object of this type is `nothing`

4 Likes

Both are working, but this one looks more “pythonic”, so I choose that as a solution. Thank you