Skip to content

Instantly share code, notes, and snippets.

@mem-memov

mem-memov/insertInOrder

Created October 6, 2019 13:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mem-memov/b41a991d4fb06a86b7a99ccbd34954f8 to your computer and use it in GitHub Desktop.
Save mem-memov/b41a991d4fb06a86b7a99ccbd34954f8 to your computer and use it in GitHub Desktop.
Download ZIP
insertInOrder
Raw
insertInOrder
insertInOrder :: Int -> Tree -> Tree
insertInOrder x Leaf = Node x Leaf Leaf
insertInOrder x node@(Node y _ _)
| x == y = node
insertInOrder x (Node y left@(Node ly _ _) Leaf)
| x > ly && x < y = Node x left Leaf
| x < ly = Node y (insertInOrder x left) Leaf
| x > y = Node y left (insertInOrder x Leaf)
insertInOrder x (Node y Leaf right@(Node ry _ _))
| x > y && x < ry = Node x Leaf right
| x > ry = Node y Leaf (insertInOrder x right)
| x < y = Node y (insertInOrder x Leaf) right
insertInOrder x (Node y left@(Node ly _ _) right@(Node ry _ _))
| x > ly && x < y = Node x left right
| x < ly = Node y (insertInOrder x left) right
| x > y = Node y left (insertInOrder x right)
| x > y && x < ry = Node x left right
| x > ry = Node y left (insertInOrder x right)
| x < y = Node y (insertInOrder x left) right
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment