CODEWITHSUNDEEP
c
azimov308
azimov308

Reputation: 27

How would I make a binary search tree work with a list of alphabetized words for a spell checker?

Mainly what I'm asking is, does the root node have to be equal to NULL to make leaves of characters ranging from a-z? From the examples online, the root node is a specific letter, for this example 'a', and then everything else follows. Though, how would I then create the words that start with the letter 'b'?

What I had in mind was have NULL be the root node, then say you had cap, carts, cat. You'd make a tree going:

NULL -> 'c' -> 'a' -> 'p' -> '\0'

then, you implement carts, by checking string[n] until it doesn't equal the letter in the tree and makes a new leaf and continues.

NULL -> 'c' -> 'a' -> 'p' -> '\0'
                |
                v
               'r' -> 't' -> 's' -> '\0'

now lets say I want to add a word that doesn't start with c, like pen.

'p'  -> 'e' -> 'n' -> '\0'
 ^
 |
NULL -> 'c' -> 'a' -> 'p' -> '\0'
                |
                v
               'r' -> 't' -> 's' -> '\0'

Am I on the right path with this?

Upvotes: 0

Views: 619

Answers (1)

chmike
chmike

Reputation: 22154

You can’t use a binary tree to store words because there can be more than two distinct letters after a letter.

What you need is called an m-ary tree. See this wikipedia page for a description.

Regarding the NULL at the start, it doesn’t make much sense. The root pointer must hold the address of the top node of the tree. It can’t be NULL if the tree is not empty.

It is unclear from you explanation if the NULL was for the letter. Anyway, a binary tree can have only at most two distinct successors to a node.

Upvotes: 2

Related Questions