# How to create tree from struct

**URL:** <https://discourse.julialang.org/t/how-to-create-tree-from-struct/39372>\
**Category:** General Usage\
**Tags:** question, data\_structures, self-reference\
**Created:** [May 12, 2020, 10:01pm UTC](https://discourse.julialang.org/t/how-to-create-tree-from-struct/39372 "2020-05-12T22:01:08Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![wiktorkujawa](https://avatars.discourse-cdn.com/v4/letter/w/bc8723/32.png) [@wiktorkujawa](https://discourse.julialang.org/u/wiktorkujawa)\
**Post date:** [May 12, 2020, 10:01pm UTC](https://discourse.julialang.org/t/how-to-create-tree-from-struct/39372/1 "2020-05-12T22:01:08Z")

</div>

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

```julia
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:

```julia
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.

---

<div class="post-metadata">

**Author:** ![pixel27](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pixel27/32/8902_2.png) [@pixel27](https://discourse.julialang.org/u/pixel27)\
**Post date:** [May 12, 2020, 11:03pm UTC](https://discourse.julialang.org/t/how-to-create-tree-from-struct/39372/2 "2020-05-12T23:03:40Z")

</div>

```julia
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.

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [May 13, 2020, 5:09am UTC](https://discourse.julialang.org/t/how-to-create-tree-from-struct/39372/3 "2020-05-13T05:09:42Z")

</div>

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](https://docs.julialang.org/en/v1/manual/constructors/#man-inner-constructor-methods-1) and  
[incomplete initialization](https://docs.julialang.org/en/v1/manual/constructors/#Incomplete-Initialization-1). So, your example can be rewritten as

```julia
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

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

```

and for `height` function:

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

height(root)
# 3

```

---

<div class="post-metadata">

**Author:** ![Skoffer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/skoffer/32/378_2.png) [@Skoffer](https://discourse.julialang.org/u/Skoffer)\
**Post date:** [May 13, 2020, 5:16am UTC](https://discourse.julialang.org/t/how-to-create-tree-from-struct/39372/4 "2020-05-13T05:16:25Z")

</div>

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

```julia
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`

---

<div class="post-metadata">

**Author:** ![wiktorkujawa](https://avatars.discourse-cdn.com/v4/letter/w/bc8723/32.png) [@wiktorkujawa](https://discourse.julialang.org/u/wiktorkujawa)\
**Post date:** [May 13, 2020, 9:08am UTC](https://discourse.julialang.org/t/how-to-create-tree-from-struct/39372/5 "2020-05-13T09:08:46Z")

</div>

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