12 votes

Programming Challenge: Construct and traverse a binary tree.

Posted by Emerald_Knight
Tags: coding, challenge.programming

It's that time of week again! For this week's programming challenge, I thought I would focus on data structures.

Goal: Construct a binary tree data structure. It may handle any data type you choose, but you must handle sorting correctly. You must also provide a print function that prints each value in the tree on a new line, and the values must be printed in strictly increasing order.

If you're unfamiliar with this data structure, it's a structure that starts with a single "root" node, and this root can have a left child, right child, both, or neither. Each of these child nodes is exactly the same as the root node, except the root has no parent. This branching structure is why it's called a tree. Furthermore, left descendants always have values smaller than the parent, and right descendants always have larger values.

11 comments

  1. [4]
    dnaq
    Link
    data Tree a = Node a (Tree a) (Tree a) | Leaf empty :: Tree a empty = Leaf insert :: (Eq a, Ord a) => Tree a -> a -> Tree a insert Empty x = Node x Leaf Leaf insert (Node y l r) x | x <= y =...
    data Tree a = Node a (Tree a) (Tree a) | Leaf

empty :: Tree a
empty = Leaf

insert :: (Eq a, Ord a) => Tree a -> a -> Tree a
insert Empty x = Node x Leaf Leaf
insert (Node y l r) x | x <= y = insert l x
                                  | otherwise = insert r x

toList :: Tree a => [a]
toList Leaf = []
toList (Node x l r) = toList l ++ [x] ++ toList r

printTree :: (Show a) => Tree a -> IO ()
printTree = mapM (putStrLn . show) . toList

    Guess the language?

    This is basically the simplest possible implementation and there is a completely unnecessary conversion to a (lazy) list in the code.

    In reality you would write something like:

    data Tree a = ... deriving (Functor, Foldable, Traversable)

    and get all of the traversal code for free.

    3 votes
    1. [2]
      zoec
      (edited )
      Link Parent
      Thanks for this. I'm learning Haskell and it's nice to encounter it here and there.

      Thanks for this. I'm learning Haskell and it's nice to encounter it here and there.

      3 votes
      1. dnaq
        Link Parent
        It’s a good language to learn, even if you don’t use it daily. Some of the more complicated concepts might hurt your brain a bit, and some of the abstractions can seem really weird at the...

        It’s a good language to learn, even if you don’t use it daily. Some of the more complicated concepts might hurt your brain a bit, and some of the abstractions can seem really weird at the beginning (which is the reason there are thousands of monad tutorial), but once you realize what you can do with the abstractions then it’ll fall into place.

        I find that I’m a better programmer for having learnt Haskell, even if I don’t use it daily.

    2. Emerald_Knight
      Link Parent
      Unfortunately the reply gave it away, but Haskell would've been my guess because it looks a lot like ML and is clearly a functional programming language, but doesn't quite have the same syntax....

      Unfortunately the reply gave it away, but Haskell would've been my guess because it looks a lot like ML and is clearly a functional programming language, but doesn't quite have the same syntax. Haskell's popularity makes it the best guess.

      Pretty cool to see a functional programming solution in here! Reminds me of my CS studies :)

      1 vote
  2. Emerald_Knight
    (edited )
    Link
    Again, in my heathenish ways, I'll be providing my own solution in PHP here. It's a "lazy" binary tree, in that duplicate nodes will be consolidated into a "count" field, and removed nodes that...

    Again, in my heathenish ways, I'll be providing my own solution in PHP here.

    It's a "lazy" binary tree, in that duplicate nodes will be consolidated into a "count" field, and removed nodes that reach a count of 0 will remain in place and just won't do anything, rather than actually being removed and the tree being restructured as a result.

    I've also not bothered to enforce type consistency and just assume integer inputs, and there's no return value provided to indicate success or failure of an operation. So it's also lazy because I'm being lazy and not designing this with long-term usage in mind.

    1 vote
  3. [6]
    Gyrfalcon
    (edited )
    Link
    Alright I spent longer on this than I had originally planned to, but I learned a lot while doing it. I started with some ideas from here and built up the add, display, and remove functions....

    Alright I spent longer on this than I had originally planned to, but I learned a lot while doing it. I started with some ideas from here and built up the add, display, and remove functions. Overall, looking at what I made as well as @Emerald_Knight 's solution, recursion is definitely the best way to traverse a tree structure like this.

    I wrote it in C, and I have a lot of if statements so it's longer than I think a more elegant solution would be. I have it on Pastebin for your viewing pleasure.

    EDIT: Updated pastebin link to something that hopefully doesn't leak memory OR segfault.

    1 vote
    1. [6]
      Comment deleted by author
      Link Parent
      1. [5]
        Gyrfalcon
        Link Parent
        It's actually good you haven't looked at it yet. I went to bed and realized the whole thing is leaking memory like a sieve... I'll have to fix that. C is pretty painful for me too, but that's why...

        It's actually good you haven't looked at it yet. I went to bed and realized the whole thing is leaking memory like a sieve... I'll have to fix that.

        C is pretty painful for me too, but that's why I'm trying to learn it better now. My future career path has a good chance of including high performance stuff, as well as embedded systems programming. That said, I'm currently doing a lot of Matlab for my job, and I wish for pointers every time I realize that Matlab is horrifically slow at moving things around in memory. I don't have any traumatic memories of operating systems, so to me it's more fascinating that I am writing in their "native language" so to speak.

        1 vote
        1. [4]
          Emerald_Knight
          Link Parent
          Good on you for taking the initiative! I'll be sure to take a look some other time once you've improved your code. Memory leaks are a pain.

          Good on you for taking the initiative! I'll be sure to take a look some other time once you've improved your code. Memory leaks are a pain.

          1 vote
          1. [3]
            Gyrfalcon
            Link Parent
            Thanks! It should be good now, it held up to my exhaustive testing of running it a lot of times and staring at the memory consumption on htop.

            Thanks! It should be good now, it held up to my exhaustive testing of running it a lot of times and staring at the memory consumption on htop.

            1 vote
            1. [2]
              Emerald_Knight
              Link Parent
              Bro, do you even valgrind? But seriously, I'll be sure to take a look a bit later, then :)

              Bro, do you even valgrind?

              But seriously, I'll be sure to take a look a bit later, then :)

              1 vote
              1. Gyrfalcon
                Link Parent
                I do now! No leaks in the current version, and I ran something close to the previous version to find that it leaked the vast majority of what it allocated lol.

                I do now! No leaks in the current version, and I ran something close to the previous version to find that it leaked the vast majority of what it allocated lol.

                1 vote